Wednesday, May 28, 2008

Logic attack

Reasoning with First order logic can be hard
Unfortunately, a more complex algorithm can get caught in infinite loops that are known to be impossible to guard against completely. (to be more precise, it is NP complete)”

This means that is someone creates a new web app. “Do I really think this?” where you input your beliefs. “Grass is green” “cows eat grass”->output “Cows eat something that is green” you can attack it.
Denial of Service via Algorithmic Complexity describes Attacks“. Where by sending data that they know has worst case analysis time (eg. a sort in exactly the wrong order, entries that hash to the same bucket) an attacker can massively slow down your system.

First order logic decisions are NP-complete. In the same way as hash tables can be attacked if a system reasons about first order logic maliciously crafted inputs could be used to tie up the systems resources.

No comments: