Book summary “Advances in Computers”: summary

Introduction

Modern software systems grow increasingly complex, making failures both frequent and economically devastating to your projects. You face the constant challenge of ensuring reliability, security, and correctness across massive, distributed digital environments.

Volume 108 of Advances in Computers presents cutting-edge research across software model checking, symbolic execution optimizations, software obfuscation, Internet of Things testing, and emerging software testing technologies.

Atif M. Memon gathers leading methodologies to help you secure and verify complex software. The chapters examine optimization techniques for statecharts, defensive software obfuscation, automated model checking, and robust testing frameworks for connected devices.

• How do you optimize symbolic execution for evolving state machines?
• What transformations protect your code against reverse engineering?
• How can you automate the verification of safety properties?
• Which strategies ensure effective testing for Internet of Things systems?

1. Optimizing Symbolic Execution for Rhapsody Statecharts

Model-driven engineering relies on iterative development and requires optimized verification methods like incremental analysis to handle evolving models efficiently. Software systems modeled using communicating state machines undergo multiple refinements, and repeating full verification processes after every change is tedious, necessitating optimization techniques. General Motors Corporation expressed industrial interest in improving the model-level analysis capabilities of the IBM Rhapsody tool.

Model-driven engineering requires optimized verification methods like memoization and dependency analysis to handle evolving state machines efficiently.

Statecharts and Symbolic Execution

Rhapsody Statecharts describe reactive behavior using hierarchical states and actions, which can be flattened into Mealy-like machines for symbolic execution. Statecharts extend conventional Mealy machines with advanced features like orthogonal regions and action code. To execute them symbolically, they are transformed into a semantically equivalent flattened representation called a Mealy-like machine. An example model AB consists of communicating objects itsA and itsB, where itsA has an attribute x initialized to 0 and a protocol of messages e1, e2, and e3. The initial integer value of attribute y in class B is 5.

Symbolic execution replaces concrete inputs with symbolic values to explore execution paths and generate a symbolic execution tree constrained by solver checks. By substituting inputs with symbolic variables, symbolic execution computes variable valuations and path constraints over execution paths, utilizing SMT solvers to check path constraint satisfiability. The complete symbolic execution tree of the example model has a depth of 6 and 14 symbolic execution paths identified by its leaves. Symbolic execution was first introduced in the 1970s by Clarke and King.

Memoization and Dependency Optimizations

Memoization-Based Symbolic Execution reuses results from previous runs to avoid regenerating unchanged parts of a symbolic execution tree. It stores the previous tree, identifies model differences, removes affected subtrees, marks corresponding nodes as needing updates, and reruns the symbolic execution engine only on modified parts. Applying memoized execution on the modified individual Statechart V1 and communicating Statecharts AB V1 achieved savings of approximately 43% and 52% in node reuse.

You execute the following tasks to perform memoized symbolic execution:

• Explore base symbolic execution tree or general symbolic execution tree to remove subtrees for updated transitions and mark nodes needing updates.
• Iterate over the result and set attributes needsUpdate and branchesToUpdate for un-subsumed leaf states.
• Reexplore the tree using the Adapted Nodes Update Strategy to merge results from standard symbolic execution for updated parts.
• Detect and remove any extra redundant symbolic states from the resulting tree.

Dependency-Based Symbolic Execution generates a partial view of a complete symbolic execution tree by focusing only on paths impacted by changes. It integrates change impact analysis with symbolic execution, fully exploring transitions that are updated or have data and communication dependencies, while only partially exploring unaffected transitions. Applying dependency-based execution on model version V1 and AB V1 resulted in approximately 43% savings through pruned nodes during partial exploration.

You apply these steps for dependency-based symbolic execution:

• Compute data dependences and communication dependences between model transitions.
• Identify the set of transitions impacted having dependency relations with updated transitions.
• Run symbolic execution in full-exploration mode for updated or impacted transitions and partial-exploration mode for all other transitions.

Empirical Evaluation Results

Memoized symbolic execution consistently achieves significant average savings in execution time, symbolic states, and execution paths across all tested models. It avoids redundant exploration of common execution paths between model versions by reusing the previous version's symbolic execution tree. Average time savings ranged from 56.9% up to 71.7% depending on the model. For the LGS model, memoized execution achieved an average execution time savings of 71.7% out of an initial base time of 5 minutes.

Directed symbolic execution shows higher sensitivity to subject models, achieving massive savings on some models while yielding minimal improvements on others. It uses change impact analysis to restrict exploration to parts affected by the change. Its effectiveness is strongly tied to the presence of multipath transitions and dependencies within the model. Dependency-based execution achieved an average time savings of 98.4% for the AQS model, but only 1.4% for the ACCS model due to low multipath opportunities.

2. A Tutorial on Software Obfuscation

Software obfuscation transforms programs to protect digital assets against Man-At-The-End attackers using data and code transformations.

Malicious end-users who control the hardware where a digital asset is consumed are called Man-At-The-End attackers and pose a primary threat to software confidentiality and integrity. These attackers examine software statically or dynamically using decompilers and debuggers, inspect memory states, and alter binaries or execution flows to bypass licensing or steal intellectual property.

Threats and Transformations

Obfuscation transformations modify programs into functionally equivalent ones that are harder for analysts to understand, categorized by targets such as data and code. Transformations are classified by abstraction level, transformation unit, dynamics, and target. Targets are divided into data transformations covering constants and variables, and code transformations covering logic and abstractions.

Opaque predicates are conditional expressions whose truth value is fixed and known to the obfuscator but difficult for attackers to deduce statically. They can be constructed using mathematical formulas or undecidable properties like pointer alias analysis in linked lists to create dead code branches or obscure loop termination.

Mixed Boolean-Arithmetic encodes data using linear identities involving both Boolean and arithmetic operations alongside invertible polynomial functions dependent on external inputs. This technique prevents simple deobfuscation via standard compiler optimizations like constant propagation by tying constant values to program inputs. For example, 0x87654321 is the sample integer value k encoded using a second degree polynomial with coefficients in Z / ( 2 32 ).

Advanced Obfuscation Mechanisms

White-box cryptography embeds secret cryptographic keys directly into cipher logic and lookup tables instead of storing them separately, protecting against software inspection. A 128-bit key is used in AES ciphers. To prevent direct key extraction from known specifications, implementations use techniques like wide linear encodings, perturbations, dual-ciphers, and random permutations on lookup tables. A 2 128 entries is the size of an impractical complete lookup table for AES.

Control flow flattening collapses all basic blocks of a function into a flat switch statement inside an infinite loop, hiding the original program control flow. A control variable is updated by every case to dictate the execution order, resembling an interpreter structure and forcing analysts to reorder cases correctly.

Virtualization obfuscation encodes program statements into custom bytecode and executes them using an embedded software interpreter engine. The interpreter uses a virtual program counter and a switch statement with opcode handlers to process the bytecode over a common data array representing memory.

• Map variables, function parameters, and constants to entries in a common data array representing interpreter memory.
• Map all statements in a function to a new randomly chosen language representing the interpreter instruction set architecture.
• Store the encoded bytecode inside the code array.
• Create an interpreter for the generated instruction set architecture that can execute instructions using the data array as memory.

3. Advances in Software Model Checking

Software failures impose massive financial burdens globally, highlighting the critical need for improved automated testing and verification infrastructures. As software complexity grows exponentially and infiltrates core societal domains like aviation and finance, manual testing exercises only a tiny fraction of total program states. Improved automated testing and model checking are essential to reduce these economic losses.

Software flaws cost the U.S. economy an estimated $59.5 billion annually. Globally, software flaws impose an estimated annual cost of $175 billion.

Verification Properties and Limitations

Software verification properties are broadly divided into safety properties, which ensure nothing bad happens, and liveness properties, which ensure something good eventually happens. For verification purposes, safety properties are typically formulated as a reachability problem, such as proving that programmer-inserted assert statements are completely unreachable during execution.

Most model checking algorithms are sound but incomplete due to the undecidability of the halting problem. A sound algorithm correctly declares truly safe programs as safe, while a complete algorithm declares all safe programs as safe. Because of theoretical limits, algorithms either explore a bounded subset of states or analyze a conservative abstract superset.

Symmetry reduction and partial order reduction mitigate state space explosion by grouping or pruning redundant states and transition paths. Symmetry reduction identifies equivalence classes of states using structural or process symmetries, while partial order reduction exploits the commutativity of concurrent operations to prune redundant independent transition sequences.

Bounded Model Checking and Abstraction

Symbolic execution systematically checks program paths over all input choices by converting path constraints into formulas solved by SMT or SAT solvers. Instead of executing concrete values, forward symbolic execution executes programs on symbolic values, maintaining a path condition constraint for every branching decision on the executed path.

Software model checking automates the verification of safety and liveness properties using state space reductions and abstract refinement loops.

The middle-of-three integers program produces six distinct path conditions in its execution tree that can be solved using off-the-shelf SAT solvers.

Abstraction-based model checking simplifies program state spaces into finite abstract models, using counterexample-guided abstraction refinement to recover precision iteratively. By grouping concrete states into abstract domains, such as predicate abstraction, verification can prove the total absence of errors. If spurious counterexamples emerge, the counterexample-guided abstraction refinement loop refines the abstraction with extra predicates.

The SLAM project pioneered Boolean programs and the counterexample-guided abstraction refinement loop to verify device drivers by translating C programs into abstract Boolean representations.

4. Model-Based Testing for Internet of Things Systems

Internet of Things systems require specialized model-based testing frameworks to handle scalability, protocol heterogeneity, and end-to-end security certification.

Testing Internet of Things systems introduces complex challenges due to massive scalability requirements, heterogeneous communication protocols, and critical security vulnerabilities across multiple architecture layers. Internet of Things systems span four major layers: sensor, gateway and network, management service, and application. The massive scale of connected devices combined with diverse protocols like HTTP, MQTT, and CoAP creates severe interoperability hurdles and exposes systems to cyberattacks like denial of service and man-in-the-middle attacks.

Gartner Group estimated 21 billion connected things by 2020. In 2016, there were 6.4 billion Internet of Things devices in use.

The October 2016 distributed denial of service attacks on DYN servers brought down major online services in the United States by leveraging up to 100,000 unsecured Internet of Things devices as malicious endpoints.

IoT Testing Challenges and Standards

Model-based testing automates test generation by creating formal models of system requirements and behavior, significantly reducing project maintenance and improving test coverage. You can apply the core workflow to generate executable test suites automatically.

The model-based testing process follows five main steps:

• Step 1: Creation of the model-based testing models
• Step 2: Generation of test cases
• Step 3: Concretization of the test cases
• Step 4: Execution of the test cases
• Step 5: Results analysis

Model-based testing can validate Internet of Things platform conformance against open standards by utilizing structural class diagrams and dynamic object constraint language behaviors. By modeling standardized RESTful interfaces like OMA NGSI-9/10 using UML class diagrams and object constraint language pre and postconditions, testing tools like CertifyIt can automatically generate smartsuites of test cases to ensure compliance and resolve platform interoperability issues.

Researchers tested the FIWARE data handling Generic Enabler implementation, extracting 26 test targets and generating 22 tests in approximately 10 seconds to cover the specified behavior. The FIWARE standard has a community size adopting it of 1000 start-ups and an adoption scale of 80 cities worldwide. Creating the model-based testing model required 16 person-hours in total effort, split into 4 person-hours spent modeling the static view and 12 person-hours spent modeling the dynamic view and object constraint language postconditions.

Security Certification and Automation

Large-scale end-to-end Internet of Things security testing combines multiple component models into a unified integration model driven by Business Process Model Notation.

The ARMOUR project integrated bootstrapping procedures and secure platform data storage models into a single Business Process Model Notation workflow, generating abstract test cases that are compiled into TTCN-3 executable test suites. Online model-based fuzzing combines structural model-based testing models with random test generation to rapidly expose unexpected system behaviors in uncommon contexts. Tools like MBeeTle use weighted random algorithms to generate syntactically valid test steps based on expected system behaviors without requiring malformed inputs, providing a complementary approach to traditional functional and security testing.

Experiments within the ARMOUR framework utilized the FIT Internet of Things-LAB testbed and Titan compiler to execute end-to-end security scenarios, revealing via an integrated sniffer that 92 percent of exchanged messages were unencrypted. The FIT Internet of Things research received 5.8 million Euros in funding from the French Equipex research grant program.

Model-based testing as a service implements a distributed web service architecture to handle test customization, publication, execution, and reporting over cloud infrastructures. The model-based testing as a service architecture separates responsibilities into a web front-end customization service, a publication service that generates concrete test description files, an execution service that stimulates the system under test, and a reporting service that stores results in a database.

Product security evaluation and certification follow a structured four-phase process to ensure compliance with proprietary or market requirements. Security certification verifies resistance to attacks such as replay, dictionary, denial of service, and man-in-the-middle attacks, ensuring properties like authentication, integrity, confidentiality, and availability.

Product evaluation follows specific operational steps:

• Application: A company applies a product for evaluation to obtain certification.
• An evaluation is performed through internal self-certification, a testing company belonging to the product company, or a third-party company evaluation.
• The evaluation company provides a decision on the evaluation.
• Surveillance: A periodic check on the product to ensure that the certification is still valid.

10 Key Ideas

1. Rhapsody Statecharts describe reactive behavior using hierarchical states and actions, which can be flattened into Mealy-like machines for symbolic execution.
2. Memoized-based symbolic execution reuses results from previous runs to avoid regenerating unchanged parts of a symbolic execution tree.
3. Dependency-based symbolic execution generates a partial view of a complete symbolic execution tree by focusing only on paths impacted by changes.
4. Malicious end-users who control the hardware where a digital asset is consumed are called Man-At-The-End attackers and pose a primary threat to software confidentiality and integrity.
5. Software obfuscation transforms programs to protect digital assets against Man-At-The-End attackers using data and code transformations.
6. Virtualization obfuscation encodes program statements into custom bytecode and executes them using an embedded software interpreter engine.
7. Most model checking algorithms are sound but incomplete due to the undecidability of the halting problem.
8. Abstraction-based model checking simplifies program state spaces into finite abstract models, using counterexample-guided abstraction refinement to recover precision iteratively.
9. Testing Internet of Things systems introduces complex challenges due to massive scalability requirements, heterogeneous communication protocols, and critical security vulnerabilities across multiple architecture layers.
10. Model-based testing automates test generation by creating formal models of system requirements and behavior, significantly reducing project maintenance and improving test coverage.