Controlling Combinatorial Complexity in Software and Malware Behavior Computation

Virtually all software is out of intellectual control in that no one knows its full behavior. Software Behavior Computation (SBC) is a new technology for understanding everything software does. SBC applies the mathematics of denotational semantics implemented by function composition in Functional Trace Tables (FTTs) to compute the behavior of programs, expressed as disjoint cases of conditional concurrent assignments. In some circumstances, combinatorial explosions in the number of cases can occur when calculating the behavior of sequences of multiple branching structures. This paper describes computational methods that avoid combinatorial explosions. The predicates that control branching structures such as ifthenelses can be organized into three categories: 1) Independent, resulting in no behavior case explosion, 2) Coordinated, resulting in two behavior cases, or 3) Goal-oriented, with potential exponential growth in the number of cases. Traditional FTT-based behavior computation can be augmented by two additional computational methods, namely, Single-Value Function Abstractions (SVFAs) and, introduced in this paper, Relational Trace Tables (RTTs). These methods can be applied to the three predicate categories to avoid combinatorial growth in behavior cases while maintaining mathematical correctness.