PaperlayerView exact revision on arXiv

Source-linked AI summary

NosRacer: Dynamic Detection of Race Conditions in On-Device Network Operating Systems

Runze Wu, Jingbo Zhai, Shanming Ping, Lingzhi Ouyang, Hua Duan, Qin Zou, Chengcheng Huang, Bingshe Liu, Xudong Lang, Xiaoxing Ma, Yu Huang

arXiv:2610.11875v1cs.DCcs.SE

TL;DR

Asynchronous message ordering can make identical NOS configuration commands produce different outcomes, while existing static and dynamic analyses face scale and execution-cost limits. NosRacer narrows analysis to relevant components and state, then perturbs message timing; it detected 21 race conditions with 66% precision and under 10% testing-cost increase.

  • Problem

    NOS configuration updates can produce different outcomes under different asynchronous message orderings, and subtle delayed malfunctions make races difficult to trace; existing static analysis has scale and precision limits while dynamic analysis faces high execution costs.

    Source: §1 · pp. 1–2

  • Method

    NosRacer uses a concentration phase to focus on involved components and crucial variables, then perturbs message asynchrony, grouping compatible perturbations and adaptively strengthening them.

    Source: §1 · pp. 2–3, §3.2 · p. 7

  • Results

    66% precision; NosRacer detected 15 new and reproduced 6 known race conditions in five control-plane components, with testing-cost increase below 10%.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Integrated into a production NOS's testing factory, NosRacer demonstrates that dynamic race detection can be practical for large-scale, actively developed NOSes.

    Source: §7 · p. 13

    Some detected value differences may be transient: periodic synchronization or retry can restore normal state, and developers did not consider those reports to require a fix.

    Source: §5.3.1 · p. 12

Abstract

from arXiv · show

Commercial on-device network operating systems (NOSes) run complex control planes in production routers and switches, where configuration update tasks are executed by multiple loosely coupled components through asynchronous message passing. Such executions are prone to race conditions: the same ordered input commands may produce different outcomes when messages are delivered in different orders. The race conditions are difficult to expose because they often manifest only as subtle, delayed malfunctions. Existing static analysis techniques lack scalability and precision for large-scale industrial NOSes, while dynamic ones incur substantial system-execution cost when attempting to cover the space of asynchronous message interleavings. To address the challenges above, we present NosRacer, a dynamic analysis framework for race condition detection in industrial-grade on-device NOSes. NosRacer uses a two-phase design. The concentration phase reduces analysis scope by leveraging the locality of configuration update tasks. Race condition detection is then limited to a small subset of involved components and crucial state variables, thereby reducing the detection cost. The perturbation phase proactively perturbs message asynchrony to increase the likelihood of executions with race-condition-exposing message interleavings. It keeps perturbation practical by grouping compatible perturbations for parallel execution and adaptively strengthening perturbations. We implement NosRacer in a commercial, actively developed NOS. NosRacer is integrated into the existing testing factory and used to detect race conditions in 5 key control-plane components. NosRacer achieves 66% precision and detects 21 race conditions confirmed by developers as severe bugs, while keeping the detection overhead below 10%.

1 Introduction

NosRacer addresses race conditions in asynchronous NOS configuration updates with a two-phase dynamic analysis that narrows the analysis and perturbs message timing. It was evaluated in a commercial NOS, where it found confirmed bugs with under 10% testing-cost increase.

1 Introduction

  • Race conditions let the same ordered configuration commands produce different outcomes when asynchronous messages are handled in different orders, often causing subtle malfunctions that are hard to trace.An example is a VLAN subscription left unsubscribed after ARP reads stale state; the interface then cannot forward packets.Source: §1 · pp. 1–2
  • At production scale, static analysis faces scalability and precision limits, while dynamic analysis incurs unacceptable execution costs across asynchronous interleavings.The studied NOS has 200+ control-plane components, each typically containing 5k+ variables and 10k+ functions.Source: §1 · p. 2
  • NosRacer's concentration phase exploits task locality to focus on involved components and crucial state variables, which are tracked for concurrent reads and updates.Among 27 race-condition-induced bugs, every task involved at most 8 of 200+ components, and 80% involved at most 5.Source: §1 · p. 2
  • 66% precision; NosRacer detected 15 new and reproduced 6 known race conditions across five control-plane components, with a testing-cost increase below 10%.All 21 bugs were fixed; deployment and usage cost was no more than 20 person-days.Source: §1 · p. 3
  • NosRacer consolidates compatible perturbations, runs conflicting groups in parallel, and adaptively strengthens perturbations within an estimated upper bound when attempts fail.Excessive perturbation can move execution away from the original and make detection ineffective.Source: §1 · p. 3

2 NosRacer Happen-Before Model

The happen-before model narrows race reasoning to a configuration task and a target component, then defines which operations are ordered and when concurrent accesses indicate a race.

2 NosRacer Happen-Before Model

  • The model formalizes temporal ordering among message-handler operations as the basis for identifying race conditions.It first defines configuration update tasks, then operation ordering, and derives the race definition from that ordering.Source: §2 · p. 3

2.1 Configuration Update Task

  • NosRacer selects one task and target component per run, restricting analysis to that component's state and message-handling interactions rather than system-wide interleavings.A task consists of ordered configuration commands processed by multiple components through asynchronous messages.Source: §2.1 · p. 3

2.2 Happen-before Model

  • Happen-before ordering combines handler program order, message-send causality, FIFO channel order, and the order of commands in the task.Task order preserves input-command order at a receiver; FIFO order preserves already ordered sends from one component to the same receiver.Source: §2.2 · p. 4
  • Operations are concurrent when neither happens-before the other; a concrete execution's total order is distinct from the cross-execution happen-before order.The concrete order applies within one execution, whereas happen-before is preserved across executions.Source: §2.2 · p. 4

2.3 Race Condition

  • A race is detected when the same input task reverses the order of concurrent handlers across paired executions and produces different values for a crucial variable.NosRacer checks concurrent reads and updates in test executions and aligns accesses to runtime instances; severity assessment considers effects on later message sends and handler calls.Source: §2.3 · pp. 4–5

3 NosRacer Framework

NosRacer uses concentration to narrow analysis to relevant components and crucial variables, then perturbs message asynchrony to construct executions that expose races.

3.1 Concentration

  • Among 27 real-world bugs, all involved at most 8 components and 22 at most 5; prioritized tests identify interacting components, converging within 20 cases in deployment.Source: §3.1.1 · pp. 5–6
  • Variables accessed by multiple handlers, with at least one update, are deemed crucial; AST analysis finds access sites at lower cost but with less semantic precision than IR.Source: §3.1.2 · p. 6
  • Coverage-guided preparatory runs cover crucial-variable access sites, while a happens-before operation graph uses message hashes to infer handler concurrency without logical timestamps.Source: §3.1.3 · p. 6

3.2 Perturbation

  • NosRacer seeks executions that reverse concurrent handler order while keeping test inputs unchanged, and detects a race when the crucial variable’s value differs.It pairs the perturbed access with its original concurrent access.Source: §3.2 · p. 6
  • NosRacer batches compatible delays to conserve testing budget, separates conflicting perturbations into parallel groups, and strengthens failed delays when the original access remains observable.It doubles the delay after a failed perturbation and estimates an upper bound using implementation timeouts and a small number of perturbed executions.Source: §3.2 · p. 7, §3.2.1 · p. 7, §3.2.2 · pp. 7–8

3.3 Detection and Validation

  • In deployment, NosRacer offers no strict soundness or completeness guarantees; users assess severity through behavioral divergence, outgoing-message sequences, and handler sequences.Source: §3.3 · p. 8

3.4 Discussions

  • The current design monitors simple crucial variables and behavior differences within test executions; richer structures, invariants, and state correlations may reveal broader race classes.Further perturbation mechanisms require broader assessment of system-wide impact; deployment and evaluation data will guide future work.Source: §3.4 · p. 8

4 Implementation and Integration

NosRacer combines runtime tracing with offline analysis and integrates its runs into the target NOS’s existing testing factory.

Implementation

  • Clang-based source instrumentation records crucial-variable accesses, message exchanges, and execution context; sender-side hooks inject delays during perturbation runs.Source: §4 · p. 8
  • Offline analysis identifies concurrent crucial-variable accesses, derives delay rules, and compares original and perturbed runs, matching accesses by variable identifier and recorded execution context.Source: §4 · p. 8

Integration

  • NosRacer covers 5 control-plane components, and configuring it for a new target component—using its name, relevant configuration-update test labels, and optional related-component/task hints—typically takes less than 30 minutes per component.An orchestrator manages each run as a dependency graph of test executions and offline-analysis steps.Source: §4 · p. 9

5 Evaluation

Across five production NOS components, NosRacer found developer-confirmed severe bugs and reduced detection overhead through concentration. The evaluation also reports limits in matching perturbed accesses and cases developers classified as benign.

5.1 Effectiveness

  • Bug-triggering race conditions were similar in number across target components, at four to five per component, and were associated more with asynchronous interaction patterns than component-specific functionality.Most confirmed bugs had consequences including stale or inconsistent state, forwarding errors, or service unavailability.Source: §5.1.1 · p. 9

5.1.2 From concurrent accesses to race conditions.

  • NosRacer reported 32 race conditions, 4% of over 800 observed concurrent accesses, and 20% of concurrent accesses paired with perturbed accesses.Perturbation strengthening raised the share with corresponding perturbed accesses from less than 10% to about 20%.Source: §5.1.2 · pp. 9–10

5.1 Effectiveness

  • 21 of 32 reported race conditions were confirmed as severe bugs, including 15 previously unknown bugs.NosRacer exposed all 21 using existing tests that had repeatedly passed in the testing factory.Source: §5.1 · p. 9, Table 1 · p. 10

5.2 Efficiency

  • Offline trace analysis finished within one minute per execution for all target components, while the longest per-report analysis took 15 minutes.Per report, NosRacer usually analyzed hundreds of MB of traces and spent minutes in offline analysis.Source: §5.2.2 · p. 11, Table 5 · p. 11
  • Concentration selected less than 10 interacting components (9% on average), tens to hundreds of crucial variables (24% on average), and 8% of available test cases on average.The selected tests numbered in the hundreds, from thousands or tens of thousands available per component.Source: Table 6 · p. 11, §5.2.3 · p. 11
  • 90% to 10% execution-time overhead and 65% to 20% memory overhead followed concentration; tracing overhead was at most 10% for execution time and 20% for memory.Concentration also reduced CPU utilization from 80% to 55%; enabling tracing increased it by no more than 10%.Source: §5.2.3 · p. 11, §5.2.1 · p. 11, Table 4 · p. 11

5.3 Discussion

  • Developers classified six reports as benign when differing variable values preserved task invariants or later synchronization or retry restored normal state.The authors suggest allowing developers to specify system-specific invariants to filter such reports.Source: §5.3.1 · pp. 11–12
  • Only 19% of concurrent accesses had corresponding perturbed accesses; delays above about five seconds often triggered timeout or retry paths and obscured matching accesses.The authors suggest deriving tests that place related configuration commands closer together.Source: §5.3.2 · p. 12

6 Related Work

Prior testing and formal methods have limitations for industrial NOSes, while static and dynamic race detectors face scalability, precision, and execution-cost challenges. NosRacer combines static guidance with dynamic execution evidence and probabilistic delay injection at selected points.

6 Related Work

  • System-level stress testing cannot systematically explore rare message interleavings, while formal verification is often impractical for industrial NOSes because of adoption costs.Formal methods provide rigorous guarantees under a specification, but have a high learning curve and substantial adoption cost.Source: §6 · p. 12
  • Static analysis faces path explosion and limited precision in production NOSes, where asynchronous interactions, customized optimizations, and million-line codebases challenge scalability.NosRacer uses static analysis to identify crucial variables and perturbation points, while relying mainly on dynamic execution and perturbed runs to identify suspects.Source: §6 · p. 12
  • Dynamic analysis improves precision through concrete runtime observations, but execution cost and interleaving space hinder deployment; NosRacer instead uses selected probabilistic delay injection.NosRacer reports crucial-variable value differences and subsequent behavioral differences to expose silent state corruption.Source: §6 · p. 12

7 Conclusion

NosRacer combines task-locality-based concentration with perturbation to detect race conditions in an actively developed production NOS. The conclusion identifies incremental analysis, richer severity assessment, and evaluation in other asynchronous systems as future directions.

7 Conclusion

  • NosRacer uses task locality to reduce analysis cost and perturbs message asynchrony to confirm race-condition suspects in a production NOS testing factory.The authors conclude that this integration demonstrates practical dynamic race detection for large-scale, actively developed NOSes.Source: §7 · p. 13
  • Incremental analysis could reuse traces and prior results across code revisions to reduce deployment cost in CI pipelines.This is proposed as a future direction as the NOS codebase evolves.Source: §7 · p. 13
  • Severity analysis currently examines effects on later message-sending and function-call sequences, with consistency checks, cross-component invariants, and service symptoms proposed for future work.Source: §7 · p. 13
  • Whether NosRacer’s two-phase design generalizes to distributed control systems and cloud management platforms remains an open research direction.The conclusion notes that these systems share asynchronous interactions, large execution spaces, and limited testing budgets.Source: §7 · p. 13

A Testing Factory of the Target NOS

The target NOS’s testing factory is a large-scale CI platform for development and release testing. NosRacer uses existing system-level tests, their profiles, and the factory environment.

A Testing Factory of the Target NOS

  • The testing factory runs workloads for NOS development and release testing as a large-scale CI platform.Source: A Testing Factory of the Target NOS · p. 16
  • Its system-level tests use virtualized multi-device topologies, CLI configuration commands, and injected traffic to assess NOS behavior, performance, and stability.Source: A Testing Factory of the Target NOS · p. 16
  • Configuration-update tests form a large portion of the factory’s system-level tests and validate behavior after applying configuration commands.NosRacer uses these existing tests together with their profiles and the factory execution environment.Source: A Testing Factory of the Target NOS · p. 16

A.1 Test Execution Environment

The factory schedules schema-defined test plans across a large pool of virtualized testbeds, runs their workloads, and stores execution artifacts and reports. The environment supports multi-device NOS tests from topology setup through outcome checks.

A.1 Test Execution Environment

  • The factory handles over 200,000 system-level test executions daily, with over 10,000 virtualized testbeds and over 5,000 executions running concurrently.Each test plan specifies topology, workload, and checks for test outcomes.Source: §A.1 · p. 16
  • The factory manager assigns queued plans to compatible available testbeds and can reuse suitable testbeds for plans with similar topologies.Source: §A.1 · p. 16
  • Testbed managers create the requested topology using KVM-based VMs for NOS devices, Docker containers for endpoints and auxiliary services, and virtual links.Source: §A.1 · p. 16
  • For configuration-update tests, the manager establishes the initial state, applies changes, queries device state, observes traffic, and checks expected outcomes.Source: §A.1 · p. 16
  • After execution, the factory stores logs, traffic observations, state snapshots, and results, then links analysis reports to their test plans, executions, and artifacts.Source: §A.1 · p. 16

A.2 Configuration-Update Test Cases

The testing factory maintains a large, evolving suite of configuration-update tests and profiles each test with functional labels and code-coverage information. NosRacer uses those profiles to select tests related to target components and prioritize tests that cover crucial-variable access sites.

A.2 Configuration-Update Test Cases

  • More than 200,000 configuration-update tests cover operational changes across hundreds of NOS components and thousands of configuration features.Tests establish pre-update state, apply ordered changes, and check intermediate and post-update outcomes.Source: §A.2 · p. 16
  • Each test profile combines engineer-maintained functional labels with code coverage gathered by periodically running tests with instrumentation enabled.Figure 5 shows a simplified, anonymized example profile.Source: §A.2 · pp. 16–17, Figure 5 · p. 17
  • More than 5,000 tests per target component on average enter the label-based candidate set, after which coverage prioritizes tests reaching crucial-variable access sites.The access sites are identified in §4.Source: §A.2 · p. 17
  • The testing factory supplies topology setup, execution scheduling, profile retrieval, and artifact reporting; an NOS CI environment with equivalent support can serve as NosRacer’s backend.Source: §A.2 · p. 17

B NosRacer Workflow Orchestration

The orchestrator runs NosRacer as a dependency graph of factory testbed executions and offline analyses, submitting each plan when its inputs are ready. It coordinates test selection, concentration, preparation, perturbation, and reporting.

B NosRacer Workflow Orchestration

  • The orchestrator tracks workflow-step state, submits test plans when inputs are ready, retrieves artifacts, and uses analysis results to launch follow-up plans.The workflow is represented as a dependency graph of testbed executions and offline-analysis steps.Source: B NosRacer Workflow Orchestration · p. 17
  • Initial runs instrument message passing across NOS components and execute related tests to collect traces for concentration.The resulting concentration analysis identifies interacting components, crucial variables, and selected tests.Source: B NosRacer Workflow Orchestration · p. 17
  • After concentration, the orchestrator instruments target-related components with message and variable-access hooks, then runs selected tests to produce preparatory traces.Source: B NosRacer Workflow Orchestration · p. 17
  • Offline analysis groups perturbations into test plans with delay rules; follow-up plans increase delays when an execution needs strengthening.The factory runs the perturbed tests, whose traces return to offline analysis.Source: B NosRacer Workflow Orchestration · p. 17
  • Final race-condition reports are published through the factory, with records linking perturbation groups to preparatory runs and reports to their execution artifacts.Source: B NosRacer Workflow Orchestration · p. 17

C NosRacer Implementation

NosRacer’s implementation addresses runtime context capture for ordering and value analysis, and matching access occurrences across executions when instances and traces differ. Its runtime tracing uses source-level instrumentation and hooks for variable accesses and message exchanges.

C.1 Runtime Tracing

  • Clang-based AST analysis inserts source-level instrumentation into the target component and its interacting components, using concentration’s component and variable results.Generated hooks are compiled into the NOS components and invoke a runtime library to generate traces.Source: §C.1 · pp. 17–18
  • Variable-access hooks record the source variable identifier, object address, access type, value, and call stack, with insertion points chosen to capture evaluated conditions or updated values.AST analysis classifies accesses as reads or updates, including those in conditions, loop expressions, arguments, and compound updates.Source: §C.1 · p. 18
  • Message hooks record sender, receiver, message type, call stack, and message hashes for send/receive pairing, and associate recorded incoming messages with their handler traces.Recording is limited to exchanges involving the target component or one of its interacting components; offline analysis uses the association to link variable accesses to handlers.Source: §C.1 · p. 18
  • During perturbation runs, the send-API wrapper reads delay rules and injects the specified delay before invoking the original send API.Source: §C.1 · p. 18

C.2 Offline Analysis

Offline analysis distinguishes runtime instances within an execution, then matches access occurrences across original and perturbed executions using variable and handler context rather than object addresses. It compares observed values only when recorded access sequences support reliable attribution.

C.2 Offline Analysis

  • Within each execution, offline analysis distinguishes runtime instances of a source-level crucial variable using its identifier and object address.Source: §C.2 · p. 18
  • Across executions, a perturbed access matches an original occurrence only when the crucial-variable identifier agrees and the corresponding handler executions appear in reversed order.Handlers are matched using their incoming message and the access call stack; duplicate occurrences with the same handler order are identified to avoid duplicate reports.Source: §C.2 · p. 18
  • Race detection compares observed values for matched occurrences only after checking that recorded accesses account for each value change in the task’s variable-instance sequence.An update performed while processing an unrecorded message may be missing, making attribution of a value difference unreliable.Source: §C.2 · p. 18
  • If either matched occurrence’s sequence shows a value change without a recorded update access, NosRacer excludes that pair from detection while continuing to analyze other occurrences.Source: §C.2 · p. 18
Loading 2610.11875v1…