Is Your Software on Dope? - Formal Analysis of Surreptitiously "enhanced" Programs

Pedro R. D'Argenio, Gilles Barthe, Sebastian Biewer, Bernd Finkbeiner, Holger Hermanns

Introduction

In 2015, the automotive world was rocked by the Volkswagen emissions scandal, where software was found to intentionally manipulate engine behavior to pass regulatory tests while polluting freely on the open road. This phenomenon, termed "software doping," represents a growing ethical and engineering crisis. As proprietary software becomes deeply embedded in everything from medical devices to consumer electronics, manufacturers have increasing incentives to include hidden behaviors that favor their own interests over those of the user or the public.

This paper provides the first rigorous formal framework to define, detect, and prove the existence of these surreptitious enhancements. By treating software doping not as a traditional bug, but as a violation of specific behavioral properties, the authors establish a mathematical foundation for software accountability.

The Problem: Why Doping is Not a Bug

Traditional software verification focuses on whether a program meets its specification—for example, ensuring a car's engine controller doesn't crash. Software doping is more insidious because the program often performs exactly as the manufacturer intended. The issue is not a failure of logic, but a hidden deviation in behavior based on "dubious" parameters, such as whether the device detects a test environment or a third-party component.

Before this research, there was no systematic way to specify what made a program "clean" versus "doped." The authors identify that doping is fundamentally a hyperproperty. Unlike standard properties that can be verified by looking at a single execution trace, a hyperproperty requires comparing multiple execution traces. To detect doping, one must ask: "How does the system behave in Scenario A versus Scenario B?"

Formalizing "Cleanness"

The authors introduce a hierarchy of formal definitions to categorize software behavior:

  1. Clean: A program is considered clean if it produces identical outputs for the same inputs, regardless of specific "parameters of interest" (e.g., the brand of a printer cartridge or the presence of a test rig).
  2. Robustly Clean: This definition addresses the "cheating" scenario. A program is robustly clean if small deviations from a standard test input result in outputs that remain within a predefined, reasonable distance. This targets software that behaves perfectly in a narrow "test window" but changes drastically outside of it.
  3. $f$-clean: A generalized version of the above, where a function $f$ defines the allowable relationship between input deviations and output deviations, providing a flexible framework for different regulatory requirements.

Verification Methodologies

To prove these properties, the authors propose two distinct technical approaches based on the nature of the software:

Sequential Programs

For standard sequential software, the authors employ self-composition. This technique involves conceptually running two instances of the program side-by-side with different parameters. By using weakest precondition ($wp$) reasoning, they can formally prove whether the two instances stay "in sync" or if the parameters of interest cause them to diverge.

Reactive Systems

For systems that interact continuously with their environment, such as an Engine Control Unit (ECU), the authors utilize HyperLTL. This is a temporal logic specifically designed to express hyperproperties. They leverage the MCHyper tool to automatically check if a system model satisfies the definitions of cleanness. This allows for the automated detection of "cheating hacks" in complex, state-based systems.

Experimental Evaluation

The paper demonstrates the framework using representative models based on real-world scenarios:

  • The Printer Model: A simple abstraction of a printer that checks for "compatible" versus "brand-name" cartridges, demonstrating how simple discrimination can be formally flagged.
  • The Emission Control Unit (ECU): A complex reactive model of a diesel engine's urea injection system. The authors created both a "clean" version and a "doped" version that detects test conditions.

Using the MCHyper model checker, the authors successfully verified the clean ECU model and flagged the doped model as a violation. In terms of performance, verification was highly efficient: a coarse model of the ECU was checked in less than 1 second, while a significantly more complex model with over 175,000 transitions took approximately 92 to 102 seconds.

Limitations and Future Outlook

While this framework provides a powerful starting point, several challenges remain for full-scale industrial application:

  • Scalability: HyperLTL model checking is computationally expensive (PSPACE-complete). Applying these methods to production-level codebases with millions of lines of code will require further optimization.
  • Continuous Systems: Real-world controllers often operate on continuous physical values, whereas the current experiments used discretized models. Future work will need to explore probabilistic distances and advanced static analysis to bridge this gap.
  • Formula Strengthening: Current tools often require manual intervention to "strengthen" HyperLTL formulas into forms they can process efficiently.

Conclusion

By formalizing software doping as a hyperproperty, this research moves the conversation from ethical intuition to mathematical certainty. It provides regulators and engineers with the tools necessary to hold manufacturers accountable, ensuring that the software we rely on behaves transparently and fairly in all conditions.

Summary updated

Abstract

Usually, it is the software manufacturer who employs verification or testing to ensure that the software embedded in a device meets its main objectives. However, these days we are confronted with the situation that economical or technological reasons might make a manufacturer become interested in the software slightly deviating from its main objective for dubious reasons. Examples include lock-in strategies and the $\mathrm{NO}_x$ emission scandals in automotive industry. This phenomenon is what we call software doping. It is turning more widespread as software is embedded in ever more devices of daily use. The primary contribution of this article is to provide a hierarchy of simple but solid formal definitions that enable to distinguish whether a program is clean or doped. Moreover, we show that these characterisations provide an immediate framework for analysis by using already existing verification techniques. We exemplify this by applying self-composition on sequential programs and model checking of HyperLTL formulas on reactive models.
BibTeX
@inproceedings{dargenio2017is,
  author = {Pedro R. D'Argenio and Gilles Barthe and Sebastian Biewer and Bernd Finkbeiner and Holger Hermanns},
  title = {{Is Your Software on Dope? - Formal Analysis of Surreptitiously "enhanced" Programs}},
  booktitle = {ESOP},
  year = {2017},
  doi = {10.1007/978-3-662-54434-1\_4},
}
Figure