Editing Program analysis (section)

==Static program analysis==
{{main|Static program analysis}}
In the context of program correctness, static analysis can discover vulnerabilities during the development phase of the program.<ref>Jovanovic, N., Kruegel, C., & Kirda, E. (2006, May). Pixy: A static analysis tool for detecting web application vulnerabilities. In Security and Privacy, 2006 IEEE Symposium on (pp. 6-pp). IEEE.</ref> These vulnerabilities are easier to correct than the ones found during the testing phase since static analysis leads to the root of the vulnerability.

Due to many forms of static analysis being computationally [[Undecidable problem|undecidable]], the mechanisms for performing it may not always terminate with the correct answer. This can result in either [[False positives and false negatives|false negatives]] ("no problems found" when the code does in fact have issues) or [[False positives and false negatives|false positives]], or because they may never return an incorrect answer but may also never terminate. Despite these limitations, static analysis can still be valuable: the first type of mechanism might reduce the number of vulnerabilities, while the second can sometimes provide strong assurance of the absence of certain classes of vulnerabilities.

Incorrect optimizations are highly undesirable. So, in the context of program optimization, there are two main strategies to handle computationally undecidable analysis:

# An optimizer that is expected to complete in a relatively short amount of time, such as the optimizer in an [[optimizing compiler]], may use a truncated version of an analysis that is guaranteed to complete in a finite amount of time, and guaranteed to only find correct optimizations.
# A third-party optimization tool may be implemented in such a way as to never produce an incorrect optimization, but also so that it can, in some situations, continue running indefinitely until it finds one (which may never happen). In this case, the developer using the tool would have to stop the tool and avoid running the tool on that piece of code again (or possibly modify the code to avoid tripping up the tool).

However, there is also a third strategy that is sometimes applicable for languages that are not completely specified, such as [[C (programming language)|C]]. An optimizing compiler is at liberty to generate code that does anything at runtime{{spaced ndash}} even crashes{{spaced ndash}} if it encounters source code whose semantics are unspecified by the language standard in use.

=== Control-flow ===
{{main|Control-flow analysis}}
The purpose of control-flow analysis is to obtain information about which functions can be called at various points during the execution of a program. The collected information is represented by a [[control-flow graph]] (CFG) where the nodes are instructions of the program and the edges represent the flow of control. By identifying code blocks and loops a CFG becomes a starting point for compiler-made optimizations.

=== Data-flow analysis ===
{{main|Data-flow analysis}}
Data-flow analysis is a technique designed to gather information about the values at each point of the program and how they change over time. This technique is often used by compilers to optimize the code.
One of the most well known examples of data-flow analysis is [[taint checking]], which consists of considering all variables that contain user-supplied data{{spaced endash}} which is considered "tainted", i.e. insecure{{spaced endash}} and preventing those variables from being used until they have been sanitized. This technique is often used to prevent [[SQL injection]] attacks. Taint checking can be done statically or dynamically.

=== Abstract interpretation ===
{{main|Abstract interpretation}}
Abstract interpretation allows the extraction of information about a possible execution of a program without actually executing the program. 
This information can be used by compilers to look for possible optimizations or for certifying a program against certain classes of bugs.

=== Type systems ===
{{main|Type system}}
Type systems associate types to programs that fulfill certain requirements. Their purpose is to select a subset of programs of a language that are considered correct according to a property.

* [[Type_system#Type_checking|Type checking]] – verify whether the program is accepted by the type system.

Type checking is used in programming to limit how programming objects are used and what can they do. This is done by the compiler or [[interpreter (computing)|interpreter]]. Type checking can also help prevent vulnerabilities by ensuring that a signed value isn't attributed to an unsigned variable.
Type checking can be done statically (at compile time), dynamically (at runtime) or a combination of both.

Static type information (either [[type inference|inferred]], or explicitly provided by type annotations in the source code) can also be used to do optimizations, such as replacing [[boxed type|boxed arrays]] with unboxed arrays.

=== Effect systems ===
{{main|Effect system}}
Effect systems are formal systems designed to represent the effects that executing a function or method can have. An effect codifies what is being done and with what it is being done{{spaced ndash}} usually referred to as ''effect kind'' and ''effect region'', respectively.{{clarify|date=August 2018}}

=== Model checking ===
{{main|Model checking}}
Model checking refers to strict, formal, and automated ways to check if a ''model'' (which in this context means a formal model of a piece of code, though in other contexts it can be a model of a piece of hardware) complies with a given specification. Due to the inherent finite-state nature of code, and both the specification and the code being convertible into [[logical formula|logical formulae]], it is possible to check if the system violates the specification using efficient algorithmic methods.