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.



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'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. Digital forensics for Trojans at an accessible, fixed price. For any operating system.




Reference

Dustin Fraze. Cyber Grand Challenge (CGC). https://www.darpa.mil/program/cyber-grand-challenge. 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

Worms

Why Clean-Up Hacking?







INC Logo




What Is New? | Contact | Tips


© 2015, 2016, 2017, 2018 Intrepid Net Computing. All rights reserved.