Static Code Analysis

Computer programming is an exact science in that all properties of the program and all consequences of executing it in any given environment can, in principle, be found out from the text of the program itself by purely deductive reasoning. Tony Hoare

All the information you might want is in the source code, it just needs a little digging to get it out.

Resource

[ ] https://owasp.org/www-community/controls/Static_Code_Analysis
[ ] https://owasp.org/www-community/Source_Code_Analysis_Tools
[ ] https://www.youtube.com/watch?v=4HhHER0n8ls - Static Code Analysis - A Behind-the-scenes Look • Arno Haase • GOTO 2022
[ ] https://en.wikipedia.org/wiki/List_of_tools_for_static_code_analysis
[ ] https://en.wikipedia.org/wiki/Static_program_analysis
[ ] https://blog.codacy.com/everything-you-need-to-know-about-static-code-analysis
[ ] https://shells.systems/unveiling-bughound-a-static-code-analysis-tool-based-on-elasticsearch/
[ ] https://talks.golang.org/2014/static-analysis.slide
[ ] https://engineering.fb.com/2018/11/06/developer-tools/getafix-how-facebook-tools-learn-to-fix-bugs-automatically
[ ] https://github.com/google/error-prone
[ ] Static Analysis Tools staticanalysistools.github.io
[ ] http://cppcheck.sourceforge.net
[ ] https://owasp.org/www-community/Source_Code_Analysis_Tools
[ ] https://medium.com/nucleoid/declarative-runtime-system-d48bbf52c94e

Quality Metrics From CodeClimate

https://docs.codeclimate.com/docs

Churn

This churn metric is approximately the number of times a file has changed in the last 90 days, calculated by counting the number of distinct versions of that file across commits from that time. The absolute value won't be as useful as comparing the values across files - which files change most often, what are their relative qualities, etc.? Quality issues can have a greater impact on files that churn frequently, so high churn, low quality files should be top candidates for attention.

Cognitive Complexity

Cognitive Complexity is a measure of how difficult a unit of code is to intuitively understand.

Cyclomatic Complexity (or McCabe's Complexity)

Cyclomatic complexity is a count of the linearly independent paths through source code. You can also think of this more simply as "the number of decisions a given block of code needs to make".

As cyclomatic complexity measures the number of execution paths through code, but excessive return statements can make a function harder for a human to follow because control flow jumps around. So it is recommend checking for cognitive complexity rather than cyclomatic complexity.

Engines which compute Cyclomatic Complexity

Radon provides Cyclomatic Complexity checks on both Python 2 and Python 3 code. https://github.com/rubik/radon
A Ruby static code analyzer and formatter, based on the community Ruby style guide. https://github.com/rubocop/rubocop
ESLint offers linting, complexity analysis, and style checking for your modern EcmaScript/JavaScript code. https://github.com/eslint/eslint
PHP Mess Detector PHPMD looks for several potential problems within PHP source code, like possible bugs, suboptimal code, overcomplicated expressions, and unused parameters, methods, or properties. https://github.com/pmd/pmd
PMD An extensible multilanguage static code analyzer. https://github.com/pmd/pmd

Duplication

Code Climate's duplication engine, at its heart, uses a fairly simple algorithm to decide which parts of your code are duplicated. First, source files are parsed into abstract syntax trees (ASTs). ASTs are made up of nodes: each node has a type (which might be something like "variable assignment" or "if statement"), and a set of values (which might be a variable name or another AST node representing a sub-expression). Each node is assigned a numerical mass, calculated as the number of sub-nodes plus 1. When looking for duplication, each node in each AST is compared to every other node in the parsed ASTs. Nodes have the same structure if they have the same type as each other, and if all of their sub-nodes also have the same structure. Nodes that have the same structure but different values (like 2 "variable assignment" nodes assigning variables with different names and types), are considered "similar". Nodes that have the same structure, and also have the same values are considered "identical".

https://github.com/codeclimate/codeclimate-duplication codeclimate-duplication is an engine which reports issues when it finds similar code blocks over a configurable mass threshold. It currently supported languages for this engine are: Ruby, JavaScript, Python, PHP, TypeScript, Go, Java, Swift Two flavors of duplication can raise issues:

Identical code When 2 or more blocks of code contain the exact same variable names and structure.

Similar code When 2 or more blocks of code contain the same structure, but have different contents (such as variable names or literal values). This can help catch cases where a developer has copy and pasted a section of code, leaving the structure the same, but adjusting some variable names for a different context.

Mass "Mass" refers to the size of the duplicated code. Specifically, mass is determined by the size of a code block's s-expression, after it has been parsed into a node of an Abstract Syntax Tree (AST).

Maintainability

Maintainability is an estimate of technical debt in the repo based on a standardized 10-point assessment of Duplication, Cyclomatic Complexity, Cognitive Complexity, and structural issues.

For every technical debt issue we identify during our 10-point inspection, we estimate a rough time it would take to resolve the problem. We refer to this as remediation time. It’s never perfect, but when viewed as an aggregate we find it’s a useful way to compare technical debt projects.

For files, we assign a letter rating from A to F based on the total remediation time of all of the technical debt issues that are identified. If an issue is classified as “Wontfix” or “Invalid” using our issue statuses, it will not count against the rating.

For repository-level metrics, it’s a bit more sophisticated. Over the years, we’ve found that our old GPAs tend to correlate very strongly with the size of a repository. In other words, large projects almost always score worse than small projects, reducing the value of the metric.

To make the repository-level maintainability rating more relevant, we compute a technical debt ratio, which is the total estimated remediation time divided by a very high level total estimated implementation time, based on repository size. Lower technical debt ratios are better.

Metrics

Argument count (argument-count) - Methods or functions defined with a high number of arguments
Complex logic (complex-logic) - Boolean logic that may be hard to understand
File length (file-lines) - Excessive lines of code within a single file
Identical blocks of code (identical-code) - Duplicate code which is syntactically identical (but may be formatted differently)
Method complexity (method-complexity) - Functions or methods that may be hard to understand (Cognitive Complexity)
Method count (method-count)- Classes defined with a high number of functions or methods
Method length(method-lines) - Excessive lines of code within a single function or method
Nested control flow (nested-control-flow) - Deeply nested control structures like if or case
Return statements (return-statements) - Functions or methods with a high number of return statements
Similar blocks of code (similar-code) - Duplicate code which is not identical but shares the same structure (e.g. variable names may differ)

Dependency Graph

A dependency graph is a directed graph representing dependencies of several objects towards each other. It is possible to derive an evaluation order or the absence of an evaluation order that respects the given dependencies from the dependency graph

Dependency graphs are used in: Automated software installers: They walk the graph looking for software packages that are required but not yet installed. The dependency is given by the coupling of the packages. Software build scripts such as Unix Make, Node npm install, php composer, Twitter bower install, or Apache Ant. They need to know what files have changed so only the correct files need to be recompiled. In compiler technology and formal language implementation: Instruction scheduling: Dependency graphs are computed for the operands of assembly or intermediate instructions and used to determine an optimal order for the instructions. Dead code elimination: If no side effected operation depends on a variable, this variable is considered dead and can be removed. Dynamic graph analytics: GraphBolt and KickStarter capture value dependencies for incremental computing when graph structure changes. Spreadsheet calculators. They need to derive a correct calculation order similar to that one in the example used in this article. Web Forms standards such as XForms to know what visual elements to update if data in the model changes. Video games, especially puzzle and adventure video games, which are frequently designed as a graph of dependent relationships between in-game actions.

Call Graph

A call graph (also known as a call multigraph is a control-flow graph, which represents calling relationships between subroutines in a computer program. Each node represents a procedure and each edge (f, g) indicates that procedure f calls procedure g. Thus, a cycle in the graph indicates recursive procedure calls. Call graphs can be dynamic or static. A dynamic call graph is a record of an execution of the program, for example as output by a profiler. Thus, a dynamic call graph can be exact, but only describes one run of the program. A static call graph is a call graph intended to represent every possible run of the program. The exact static call graph is an undecidable problem, so static call graph algorithms are generally over-approximations. That is, every call relationship that occurs is represented in the graph, and possibly also some call relationships that would never occur in actual runs of the program.

Call graphs can be defined to represent varying degrees of precision. A more precise call graph more precisely approximates the behavior of the real program, at the cost of taking longer to compute and more memory to store. The most precise call graph is fully context-sensitive, which means that for each procedure, the graph contains a separate node for each call stack that procedure can be activated with. A fully context-sensitive call graph is called a calling context tree. This can be computed dynamically easily, although it may take up a large amount of memory. Calling context trees are usually not computed statically, because it would take too long for a large program. The least precise call graph is context-insensitive, which means that there is only one node for each procedure.

With languages that feature dynamic dispatch, such as Java and C++, computing a static call graph precisely requires alias analysis results. Conversely, computing precise aliasing requires a call graph. Many static analysis systems solve the apparent infinite regress by computing both simultaneously.

Call graphs can be used in different ways. One simple application of call graphs is finding procedures that are never called. Call graphs can act as documentation for humans to understand programs.[6] They can also serve as basis for further analyses, such as an analysis that tracks the flow of values between procedures, or change impact prediction.[7] Call graphs can also be used to detect anomalies of program execution or code injection attacks.[8]

https://en.wikipedia.org/wiki/Call_graph

Static call graph for getting call graphs without running application:

C/C++ Sourcetrail creates a static call graph, that can be dynamically explored by the user. Also supports Python and Java doxygen : Uses Graphviz to generate static call/inheritance diagrams cflow : GNU cflow is able to generate the direct and inverted call graph of a C program egypt : a small Perl script that uses gcc and Graphviz to generate the static call graph of a C program. Analizo: calculates source code metrics, generates dependency graphs. CCTree : Native Vim plugin that can display static call graphs by reading a cscope database. Works for C programs. codeviz : a static call graph generator (the program is not run). Implemented as a patch to gcc; works for C and C++ programs. calltree.sh : Bash shell functions that glue together cscope, graphviz, and a sampling of dot-rendering tools to display "caller" and "callee" relationships above, below, and/or between the C functions you specify. tceetree : like calltree.sh, it connects Cscope and Graphviz, but it is an executable rather than a bash script.

Go go-callvis : an interactive call graph generator for Go programs whose output can be drawn with Graphviz

.Net NDepend :is a static analysis tool for .NET code. This tool supports a large number of code metrics, allows for visualization of dependencies using directed graphs and dependency matrix.

PHP, Perl and Python Devel::NYTProf : a Perl performance analyser and call chart generator phpCallGraph : a call graph generator for PHP programs that uses Graphviz. It is written in PHP and requires at least PHP 5.2. pycallgraph : a call graph generator for Python programs that uses Graphviz. pyan : a static call graph generator for Python programs that uses Graphviz. gprof2dot : A call graph generator written in Python that converts profiling data for many languages/runtimes to a Graphviz callgraph. code2flow: A call graph generator for Python and Javascript programs that uses Graphviz rcviz : Python module for rendering runtime-generated call graphs with Graphviz. Each node represents an invocation of a function with the parameters passed to it and the return value.

XQuery XQuery Call Graphs from the XQuery Wikibook: A call graph generator for an XQuery function module that uses Graphviz

Change Impact Analysis

Change impact analysis (IA) is defined by Bohnner and Arnold as "identifying the potential consequences of a change, or estimating what needs to be modified to accomplish a change", and they focus on IA in terms of scoping changes within the details of a design. In contrast, Pfleeger and Atlee focus on the risks associated with changes and state that IA is: "the evaluation of the many risks associated with the change, including estimates of the effects on resources, effort, and schedule". Both the design details and risks associated with modifications are critical to performing IA within the change management processes. A technical colloquial term is also mentioned sometimes in this context, dependency hell.

IA techniques can be classified into three types: Trace Dependency Experiential

Bohner and Arnold identify two classes of IA, traceability and dependency IA. In traceability IA, links between requirements, specifications, design elements, and tests are captured, and these relationships can be analysed to determine the scope of an initiating change.[5] In dependency IA, linkages between parts, variables, logic, modules etc. are assessed to determine the consequences of an initiating change. Dependency IA occurs at a more detailed level than traceability IA. Within software design, static and dynamic algorithms can be run on code to perform dependency IA. Static methods focus on the program structure, while dynamic algorithms gather information about program behavior at run-time.

Literature and engineering practice also suggest a third type of IA, experiential IA, in that the impact of changes is often determined using expert design knowledge. Review meeting protocols, informal team discussions, and individual engineering judgement can all be used to determine the consequences of a modification.

Dependencies are also declared in source code. MetaData can be used to understand the dependencies via Static analysis.

Static Type Checking

Static type checking is the process of verifying the type safety of a program based on analysis of a program's text (source code). If a program passes a static type checker, then the program is guaranteed to satisfy some set of type safety properties for all possible inputs.

Static type checking can be considered a limited form of program verification (see type safety), and in a type-safe language, can be considered also an optimization. If a compiler can prove that a program is well-typed, then it does not need to emit dynamic safety checks, allowing the resulting compiled binary to run faster and to be smaller.

Static type checking for Turing-complete languages is inherently conservative. That is, if a type system is both sound (meaning that it rejects all incorrect programs) and decidable (meaning that it is possible to write an algorithm that determines whether a program is well-typed), then it must be incomplete (meaning there are correct programs, which are also rejected, even though they do not encounter runtime errors).[6] For example, consider a program containing the code:

if <complex test> then <do something> else <signal that there is a type error>

Even if the expression always evaluates to true at run-time, most type checkers will reject the program as ill-typed, because it is difficult (if not impossible) for a static analyzer to determine that the else branch will not be taken.[7] Conversely, a static type checker will quickly detect type errors in rarely used code paths. Without static type checking, even code coverage tests with 100% coverage may be unable to find such type errors. The tests may fail to detect such type errors, because the combination of all places where values are created and all places where a certain value is used must be taken into account.

A number of useful and common programming language features cannot be checked statically, such as downcasting. Thus, many languages will have both static and dynamic type checking; the static type checker verifies what it can, and dynamic checks verify the rest.

Many languages with static type checking provide a way to bypass the type checker. Some languages allow programmers to choose between static and dynamic type safety. For example, C# distinguishes between statically-typed and dynamically-typed variables. Uses of the former are checked statically, whereas uses of the latter are checked dynamically. Other languages allow writing code that is not type-safe; for example, in C, programmers can freely cast a value between any two types that have the same size, effectively subverting the type concept.

For a list of languages with static type checking, see the category for statically-typed languages.

https://en.wikipedia.org/wiki/Category:Statically_typed_programming_languages

Extended static checking (ESC)

ESC is a collective name in computer science for a range of techniques for statically checking the correctness of various program constraints. ESC can be thought of as an extended form of type checking. As with type checking, ESC is performed automatically at compile time (i.e. without human intervention). This distinguishes it from more general approaches to the formal verification of software, which typically rely on human-generated proofs. Furthermore, it promotes practicality over soundness, in that it aims to dramatically reduce the number of false positives (overestimated errors that are not real errors, that is, ESC over strictness) at the cost of introducing some false negatives (real ESC underestimation error, but that need no programmer's attention, or are not targeted by ESC). ESC can identify a range of errors which are currently outside the scope of a type checker, including division by zero, array out of bounds, integer overflow and null dereferences.

Its roots originate from more simplistic static checking techniques, such as static debugging or Lint (software) and FindBugs.

Lint, or a linter, is a static code analysis tool used to flag programming errors, bugs, stylistic errors, and suspicious constructs.[4] The term originates from a Unix utility that examined C language source code.

FindBugs is an open-source static code analyser created by Bill Pugh and David Hovemeyer which detects possible bugs in Java programs. Potential errors are classified in four ranks: (i) scariest, (ii) scary, (iii) troubling and (iv) of concern. This is a hint to the developer about their possible impact or severity. FindBugs operates on Java bytecode, rather than source code.

anitsh / til