22.12.25 (inclusive)

monetary

Idea

ICT tasks

Произвольный код

Information processing and transformation

Software/ IS

Let's consider an arbitrary program P in one of the supported languages. Let's define the semantic property of S(P): "there is a execution of P and input data x, which generates a vulnerable data stream (for example, an unprepared SQL query with user input)." Customer's requirement for the Check(P) algorithm: • if S(P) is true, Check(P) must return VULNERABLE; • if S(P) is false, Check(P) must return SAFE; • Check(P) always completes in a finite amount of time. The S property is a non—trivial semantic property of program behavior, not the syntax of the source code. Classical results of computability theory (in particular, Rice's theorem) state that for any nontrivial semantic characteristic there is no universal algorithm that correctly solves the problem for all programs. This directly hits the original requirement: universal Check(P) is strictly impossible.

In fact, we were expected to solve a class of problems that are theoretically unsolvable for arbitrary programs. We can: • severely limit supported languages and code patterns; • assume the probabilistic nature of the conclusions (heuristic mode); • Rely on a combination of static and dynamic analysis. But a universal "oracle of vulnerabilities" that correctly responds SAFE/VULNERABLE for any possible program cannot exist. This is what makes the initial task fundamentally unsolvable, and not just "difficult to implement."

Sergeev I.A.