Use your computer fearlessly.

Mission Services Articles Research

everyone: older news

business: Intractable Cybersecurity, Quantum Communications

Impossible Problems in Computer Security

by Brent Kirkpatrick

(Date Published: .)

The DARPA Cyber Grand Challenge was oversold.

Transcript (txt)

In 2016, DARPA conducted a contest to try to solve an intractable problem, that of automatically identifying security vulnerabilities. Put more technically, they asked teams to write algorithms designed to decide an undecidable problem. New mathematical proofs, published this year, demonstrate that automated solutions to computer security vulnerabilities are impossible (see article: Computer Security is Algorithmically Intractable).

DARPA oversold their Cyber Grand Challenge. Their web site says that the goal of their Cyber Grand Challenge was to create "automated defense systems capable of reasoning about flaws" or vulnerabilities in computer programs. They go on to describe this effort as a "breakthrough". Indeed, they are trying to solve an algorithmically intractable problem, that of detecting buffer over-run vulnerabilities. They oversold solutions to their challenge, because they failed to characterize the difficulties involved.

DARPA Cyber Grand Challenge web site screen shot

DARPA's imagined breakthrough will not happen. The math proves that their goal is impossible to achieve with an algorithm. The following problems are intractable for algorithms:

  1. doing digital forensics,
  2. detecting hacking, and
  3. detecting buffer over-runs.
These problems will never be solved by computer programs that have guarantees.

There are no silver bullets. The search for silver bullets is whimsical at best. I would encourage all of my colleagues to work on problems that are tractable. Computer security should be done by solving one small, tractable problem at a time.

Please contact us at Intrepid Net Computing if you need solutions to cyberattacks.

Trojan Hunter image

Trojan Hunter (TM). Digital forensics for Trojans at an accessible, fixed price. For any operating system.


Dustin Fraze. Cyber Grand Challenge (CGC). Accessed: Sept. 17, 2018.

Brent Kirkpatrick. Computer Security is Algorithmically Intractable. (whitepaper) 2018.

Brent Kirkpatrick. Computer Security is Algorithmically Intractable. Aug 16, 2018

Business Articles

What is Wrong with Cyberinsurance?

Computer Security is Algorithmically Intractable

Quantum Communications

New Technologies for a New Cybersecurity Marketplace

Panther Shadow: A Linux Worm


Why Clean-Up Hacking?

INC Logo

What Is New? | Contact | Tips

© 2015-2021 Intrepid Net Computing. All rights reserved.