View source for Program analysis

{{Short description|Process of analyzing computer program behavior}}
{{Other uses}}
{{More citations needed|date=February 2018}}
{{Software development process}}
In [[computer science]], '''program analysis'''<ref>Nielson, F., Nielson, H. R., & Hankin, C. (2015). [https://books.google.com/books?id=YseqCAAAQBAJ Principles of program analysis]. Springer.</ref> is the process of analyzing the behavior of computer programs regarding a property such as correctness, robustness, safety and liveness. 
Program analysis focuses on two major areas: [[program optimization]] and [[program correctness]]. The first focuses on improving the program’s performance while reducing the resource usage while the latter focuses on ensuring that the program does what it is supposed to do.

Program analysis can be performed without executing the program ([[static program analysis]]), during runtime ([[dynamic program analysis]]) or in a combination of both.

==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.

==Dynamic program analysis==
{{main|Dynamic program analysis}}
Dynamic analysis can use runtime knowledge of the program to increase the precision of the analysis, while also providing runtime protection, but it can only analyze a single execution of the problem and might degrade the program’s performance due to the runtime checks.

=== Testing ===
{{main|Software testing}}
Software should be tested to ensure its quality and that it performs as it is supposed to in a reliable manner, and that it won’t create conflicts with other software that may function alongside it. The tests are performed by executing the program with an input and evaluating its behavior and the produced output.
Even if no security requirements are specified, additional [[security testing]] should be performed to ensure that an attacker can’t tamper with the software and steal information, disrupt the software’s normal operations, or use it as a pivot to attack its users.

=== Monitoring ===
Program monitoring records and logs different kinds of information about the program such as resource usage, events, and interactions, so that it can be reviewed to find or pinpoint causes of abnormal behavior. Furthermore, it can be used to perform security audits. Automated monitoring of programs is sometimes referred to as [[runtime verification]].

=== Program slicing ===
{{main|Program slicing}}
For a given subset of a program’s behavior, program slicing consists of reducing the program to the minimum form that still produces the selected behavior. The reduced program is called a “slice” and is a faithful representation of the original program within the domain of the specified behavior subset. 
Generally, finding a slice is an unsolvable problem, but by specifying the target behavior subset by the values of a set of variables, it is possible to obtain approximate slices using a data-flow algorithm. These slices are usually used by developers during debugging to locate the source of errors.

==See also==
*[[Automated code review]]
*[[Language-based security]]
*[[Polyvariance]]
*[[Profiling (computer programming)]]
*[[Program verification]]
*[[Termination analysis]]

==References==
{{Reflist}}

== Further reading ==
* {{cite book |author-first1=Hiralal |author-last1=Agrawal |author-first2=Joseph R. |author-last2=Horgan |title=Dynamic program slicing|url=https://www.cs.columbia.edu/~junfeng/08fa-e6998/sched/readings/slicing.pdf}}
* {{cite book |author-first1=Wang |author-last1=Chunlei |author-first2=Zhao |author-last2=Gang |author-first3=Dai |author-last3=Yiqi |chapter=An Efficient Control Flow Security Analysis Approach for Binary Executables|doi=10.1109/ICCSIT.2009.5234950 |title=2009 2nd IEEE International Conference on Computer Science and Information Technology |pages=272–276 |year=2009 |isbn=978-1-4244-4519-6 |s2cid=10551500 }}
* {{cite book |author-first1=Flemming |author-last1=Nielson |author-first2=Hanne Riis |author-last2=Nielson|author2-link=Hanne Riis Nielson |author-first3=Chris |author-last3=Hankin |title=Principles of Program Analysis |publisher=[[Springer Science+Business Media]] |date=2005}}

==External links==
*{{Commonscatinline}}

{{Program analysis}}
[[Category:Program analysis| ]]