The Complexity of Data-Free Nfer

Sean Kauffman, Kim Guldstrand Larsen, Martin Zimmermann

Introduction

In the domain of Runtime Verification (RV), the ability to monitor and interpret system execution traces is paramount. nfer is a logic and toolset originally developed at NASA’s Jet Propulsion Laboratory to analyze event traces from complex systems like spacecraft and autonomous vehicles. Unlike traditional monitors that simply flag boolean violations, nfer constructs a hierarchy of "intervals"—labeled time periods—that provide a structured, human-readable abstraction of raw system logs.

While the full nfer language is highly expressive, its computational complexity can be prohibitive. This research investigates the data-free fragment of nfer. By abstracting away specific data values (e.g., sensor readings) and focusing exclusively on the temporal relationships and labels of events (e.g., Engine_Start, Valve_Open), the authors seek to identify the theoretical boundaries of tractability for this logic.

Problem Definition

The study focuses on two fundamental computational problems:

  1. Evaluation: Given a specific event trace and a set of nfer rules, what intervals are produced?
  2. Satisfiability: Given a set of nfer rules, does there exist any possible trace that could trigger a specific rule?

Satisfiability is particularly critical for developers; it allows for the detection of "dead" rules—specifications that can never be met—thereby improving the reliability of the monitoring system itself.

Methodology and Theoretical Reductions

To map the complexity of these problems, the authors employ several formal techniques:

Reduction from CFG Intersection

To prove the undecidability of the full data-free nfer fragment, the authors demonstrate that the logic can simulate the intersection of two Context-Free Grammars (CFGs). Since determining whether two CFGs share a common string is a classic undecidable problem, it follows that determining the satisfiability of a general nfer specification is also undecidable.

Monadic First-Order Logic (MFO)

For "cycle-free" fragments—where rules do not have recursive dependencies—the authors translate nfer specifications into Monadic First-Order Logic over strings. This mapping allows them to utilize established decidability results for MFO, though the complexity remains high (NExpTime-hard).

Producibility Algorithms

For the "inclusive-only" fragment, the authors develop a polynomial-time algorithm. This approach focuses on "duration-sensitive producibility," checking if an interval can be generated based on event reachability and physical temporal constraints. For instance, it ensures that rules requiring an overlap are not applied to zero-duration atomic events, which physically cannot overlap.

Key Insights: The Role of Negation and Monotonicity

The research highlights a critical "aha moment" regarding the source of undecidability: exclusive rules. These rules trigger only in the absence of a specific interval, effectively acting as a form of negation. When combined with recursion, this allows nfer to simulate complex, non-regular languages.

Conversely, inclusive rules (e.g., "If interval A is followed by interval B, create interval C") are monotone. In an inclusive-only system, adding more events to a trace can only generate more intervals; it can never invalidate an existing one. This monotonicity is the key to making the inclusive-only fragment's satisfiability checkable in polynomial time ($O(n^2)$ relative to the number of rules).

Key Results and Complexity Bounds

The paper establishes a clear hierarchy of complexity for data-free nfer:

  • Evaluation: Confirmed to be in PTime. Running nfer on a log file is efficient, regardless of whether the rules are cyclic or use exclusive logic.
  • Full Data-Free Satisfiability: Proven undecidable.
  • Inclusive-Only Satisfiability: Proven to be in PTime.
  • Cycle-Free Satisfiability: Proven decidable, but NExpTime-hard, suggesting significant computational difficulty even without recursion.

Conclusion and Future Directions

This work provides a rigorous complexity analysis of the data-free nfer fragment, offering a roadmap for tool developers. While the full logic is undecidable, the identification of the PTime inclusive-only fragment provides a practical subset for robust automated debugging of system specifications. The authors also reference the Sequential Sense-Process-Send (SSPS) dataset as a real-world context where these data-free applications are relevant.

Future research directions include:

  • Tightening Bounds: Confirming if cycle-free satisfiability is NExpTime-complete.
  • Finite-Data nfer: Investigating fragments where data comes from a discrete, finite set (e.g., enums), which may offer a balance between expressivity and tractability.
  • Universality: Addressing the "universality problem"—determining if every possible trace satisfies a rule—which is essential for verifying safety-critical monitors.

Summary updated

BibTeX
@inproceedings{kauffman2024complexity,
  author = {Sean Kauffman and Kim Guldstrand Larsen and Martin Zimmermann},
  title = {{The Complexity of Data-Free Nfer}},
  booktitle = {RV},
  year = {2024},
  doi = {10.1007/978-3-031-74234-7\_11},
}
Figure