Dynamic program analysis

From HandWiki
Short description: Analysis of computer software that is performed by executing the program

Dynamic program analysis is analysis of computer software that involves executing the program in question (as opposed to static program analysis, which does not). Dynamic program analysis includes familiar techniques from software engineering such as unit testing, debugging, and measuring code coverage, but also includes lesser-known techniques like program slicing and invariant inference. Dynamic program analysis is widely applied in security in the form of runtime memory error detection, fuzzing, dynamic symbolic execution, and taint tracking.

For dynamic program analysis to be effective, the target program must be executed with sufficient test inputs[1] to address the ranges of possible inputs and outputs. Software testing measures, such as code coverage, and tools such as mutation testing, are used to try to identify cases where testing is inadequate.

For dynamic analysis, care must be taken to minimize the effect that instrumentation has on the execution (including temporal properties) of the target program.[why?][needs context] Unit tests, integration tests, system tests and acceptance tests are forms of dynamic testing.[2]

Types of dynamic analysis

Code coverage

Computing the code coverage according to a test suite or a workload is a standard dynamic analysis technique. It identifies cases where code has not been executed during tests—distinguishing between code that is “covered” and code that is not.

This form of analysis identifies negatives (code that is not tested), but does not identify positives (it cannot identify if code has been adequately tested—even for code with “100% coverage”). Code can be caused to be executed by an automated test system, resulting in “code coverage”, even if the “tests” do not actually test anything about what that code does.

  • Gcov is the GNU source code coverage program.
  • VB Watch injects dynamic analysis code into Visual Basic programs to monitor code coverage, call stack, execution trace, instantiated objects and variables.

Dynamic testing

Main page: Dynamic testing

Dynamic testing involves executing a program on a set of test cases.

Memory error detection

  • AddressSanitizer: Memory error detection for Linux, macOS, Windows, and more. Part of LLVM.
  • BoundsChecker: Memory error detection for Windows based applications. Part of Micro Focus DevPartner.
  • Dmalloc: Library for checking memory allocation and leaks. Software must be recompiled, and all files must include the special C header file dmalloc.h.
  • Intel Inspector: Dynamic memory error debugger for C, C++, and Fortran applications that run on Windows and Linux.
  • Purify: Mainly memory corruption detection and memory leak detection.
  • Valgrind: Runs programs on a virtual processor and can detect memory errors (e.g., misuse of malloc and free) and race conditions in multithread programs.

Fuzzing

Main page: Fuzzing

Fuzzing is a testing technique that involves executing a program on a wide variety of inputs; often these inputs are randomly generated (at least in part). Gray-box fuzzers use code coverage to guide input generation.

Dynamic symbolic execution

Main page: Concolic testing

Dynamic symbolic execution (also known as DSE or concolic execution) involves executing a test program on a concrete input, collecting the path constraints associated with the execution, and using a constraint solver (generally, an SMT solver) to generate new inputs that would cause the program to take a different control-flow path, thus increasing code coverage of the test suite.[3] DSE can considered a type of fuzzing ("white-box" fuzzing).

Dynamic data-flow analysis

Dynamic data-flow analysis tracks the flow of information from sources to sinks. Forms of dynamic data-flow analysis include dynamic taint analysis and even dynamic symbolic execution.[4][5]

Invariant inference

Daikon is an implementation of dynamic invariant detection. Daikon runs a program, observes the values that the program computes, and then reports properties that were true over the observed executions, and thus likely true over all executions.

Security analysis

Dynamic analysis can be used to detect security problems.

  • IBM Rational AppScan is a suite of application security solutions targeted for different stages of the development lifecycle. The suite includes two main dynamic analysis products: IBM Rational AppScan Standard Edition, and IBM Rational AppScan Enterprise Edition. In addition, the suite includes IBM Rational AppScan Source Edition—a static analysis tool.

Concurrency errors

  • Parasoft Jtest uses runtime error detection to expose defects such as race conditions, exceptions, resource and memory leaks, and security attack vulnerabilities.
  • Intel Inspector performs run-time threading and memory error analysis in Windows.
  • Parasoft Insure++ is a runtime memory analysis and error detection tool. Its Inuse component provides a graphical view of memory allocations over time, with specific visibility of overall heap usage, block allocations, possible outstanding leaks, etc.
  • Google's Thread Sanitizer is a data race detection tool. It instruments LLVM IR to capture racy memory accesses.

Program slicing

Main page: 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.

Performance analysis

Most performance analysis tools use dynamic program analysis techniques.[citation needed]

Techniques

Most dynamic analysis techniques are based on some kind of code instrumentation or transformation.

  • DynInst is a runtime code-patching library that is useful in developing dynamic program analysis probes and applying them to compiled executables. Dyninst does not require source code or recompilation in general, however, non-stripped executables and executables with debugging symbols are easier to instrument.
  • Iroh.js is a runtime code analysis library for JavaScript. It keeps track of the code execution path, provides runtime listeners to listen for specific executed code patterns and allows the interception and manipulation of the program's execution behavior.

See also

References

  1. Khatiwada, Saket; Tushev, Miroslav; Mahmoud, Anas (2018-01-01). "Just enough semantics: An information theoretic approach for IR-based software bug localization" (in en). Information and Software Technology 93: 45–57. doi:10.1016/j.infsof.2017.08.012. https://linkinghub.elsevier.com/retrieve/pii/S0950584916302269. 
  2. Myers, G. J. (1979). The Art of Software Testing. John Wiley and Sons.. 
  3. Chen, Ting; Zhang, Xiao-song; Guo, Shi-ze; Li, Hong-yuan; Wu, Yue (2013-09-01). "State of the art: Dynamic symbolic execution for automated test generation" (in en). Future Generation Computer Systems. Including Special sections: Cyber-enabled Distributed Computing for Ubiquitous Cloud and Network Services & Cloud Computing and Scientific Applications — Big Data, Scalable Analytics, and Beyond 29 (7): 1758–1773. doi:10.1016/j.future.2012.02.006. ISSN 0167-739X. https://www.sciencedirect.com/science/article/pii/S0167739X12000398. 
  4. Chen, Ju; Han, Wookhyun; Yin, Mingjun; Zeng, Haochen; Song, Chengyu; Lee, Byoungyoung; Yin, Heng; Shin, Insik (2022) (in en). {SYMSAN}: Time and Space Efficient Concolic Execution via Dynamic Data-flow Analysis. pp. 2531–2548. ISBN 978-1-939133-31-1. https://www.usenix.org/conference/usenixsecurity22/presentation/chen-ju. 
  5. Chang, Walter; Streiff, Brandon; Lin, Calvin (2008-10-27). "Efficient and extensible security enforcement using dynamic data flow analysis". Proceedings of the 15th ACM conference on Computer and communications security. CCS '08. New York, NY, USA: Association for Computing Machinery. pp. 39–50. doi:10.1145/1455770.1455778. ISBN 978-1-59593-810-7. https://doi.org/10.1145/1455770.1455778.