CONCURDEP: Event-Guided Analysis of Dependency Invalidation in CPython Concurrency

• Mutation, reference drops, resource release, finalization, or Python re-entry can revoke a native dependency between acquisition and use while its owner remains alive.Source: §1 · p. 1
• Across free-threaded and conventional-GIL builds, the study identifies 144 root causes, including 95 with no earlier public report of the same native root.Source: §1 · p. 2
• Source auditing confirms 1,094 of 4,273 unique production fingerprints.Source: §1 · p. 2
• All 180 matched ConcurrBench cases are classified correctly; each release takes 22.13–27.66 seconds and 670–784 MiB median peak resident memory over five runs.Source: §1 · p. 2
• CONCURDEP models failures as property-specific invalidation of recovered owner–subject–storage dependencies, unifying parallel and re-entrant execution beyond same-address conflicts.Source: §1 · p. 2
• An event-aware NCDG links dependencies to interprocedural events by live region, target identity, and execution context, while property-specific protection validates use-time obligations.Source: §1 · p. 2
• The implementation includes an analyzer, semantic catalogs, ConcurrBench, production reports, and an auditable root-evidence ledger for three CPython releases.Source: §1 · p. 2

2.1. Background

• A dependency records why a native use is valid, including required properties such as object lifetime, owner–subject membership, storage address, representation, traversal state, and buffer leases.Source: §2.1 · p. 2

2.2. Motivating Example

• In the memoryview example, release after the state check can drop the buffer export before the copy finishes, allowing a resize to replace or reclaim the storage being read.Keeping the view alive or checking its current state does not prevent later release; retaining an export through the copy protects backing-address validity, not immutable contents.Source: §2.2 · pp. 2–3

2.3. Threat Model

• The threat model covers concurrent public APIs, controlled Python callbacks or finalizers, and conforming C-API harnesses; exporters that violate the buffer protocol are outside scope.Source: §2.3 · p. 3

3. Design

• Six mechanism plugins share dependency recovery, an event-aware NCDG, and runtime-state validation to identify native uses whose required state may be invalidated.The workflow connects recovered dependencies to events and applies property-specific state and protection transfers through a shared engine.Source: §3 · p. 3, §3.4 · p. 6

3.1. Problem Formulation

• A dependency records its acquisition, uses, owner–subject relation, family, ownership, live region, stability contract, and protection.Invalidating effects include relation removal, subject destruction, storage resize, representation rebuild, lease release, resource closure, and re-entry that may mutate state; reports require a target-matched effect to make a required property possibly invalid at a use without a kill, discharge, or stabilizing reacquisition.Source: §3.1 · p. 3

3.2.1. Runtime-Semantic Normalization.

• Normalization maps C syntax and runtime APIs to consistent operations, then uses a versioned catalog and shared points-to, call-graph, and summary analyses to recover runtime semantics.The catalog captures ownership, relations, stability, effects, callbacks, argument roles, and protection; explicit API semantics override generic rules, and contradictory ownership declarations fail validation. Catalog construction draws on CPython declarations, C-API documentation, source helpers, metadata, primitives, and release diffs.Source: §3.2.1 · p. 4

3.2.2. Dependency and Live-Region Construction.

• Dependency construction follows aliases and calls to later uses, records CFG live regions, and ends a dependency at kills, stable copies, promotions, releases, or fresh acquisition.Borrowed-object uses conservatively require both subject lifetime (LIVE) and the owner–subject relation (REL); separate properties such as storage address, lease, and traversal remain distinct obligations.Source: §3.2.2 · p. 5

3.3.1. Event and Context Construction.

• The NCDG combines interprocedural control flow, events, canonical targets, and summaries to connect dependencies with local and cross-function invalidations.Events include mutations, reference drops, releases, callbacks, re-entry, finalization, blocking and foreign calls, lock operations, thread creation and join, and GIL transitions; contexts distinguish native continuations, Python and foreign threads, callbacks, finalizers, and garbage collection.Source: §3.3.1 · pp. 5–6

3.3.2. Dependency–Event Connection.

• An event is eligible for validation only if it may execute within the dependency’s live region, target a compatible object or field, and overlap through a modeled execution context.Free-threaded public entries may overlap absent ordering or joins, whereas conventional-GIL entries require explicit exposure contexts. Protection suppresses effects only when it preserves the relevant property throughout the interval and follows the invalidating operation’s synchronization protocol; incomplete modeling of critical-section suspension can overstate protection.Source: §3.3.2 · p. 6

3.4.1. Property-Specific State Propagation.

• The shared engine propagates property-specific abstract state through live CFG regions and reports a violation only when invalid state reaches a required use.It checks consumed inputs before local transfers and post-interference uses when a continuation retains a dependency; recognized protection applies only to properties it preserves, and external-entry alternatives model one event after acquisition rather than multi-event sequences at that point.Source: §3.4.1 · pp. 7–8

3.4.2. Mechanism-Specific Reporting.

• Mechanism plugins select dependencies and required properties, then evaluate transition evidence to assign candidate reports, priorities, and explanations.Results depend on the supplied compilation database, catalog, call graph, points-to result, event model, and protection abstraction; missing facts, unmodeled sequences, conditional builds, inline assembly, or external code can cause missed or infeasible reports.Source: §3.1 · p. 4, §3.4.2 · p. 8

3.4.2. Mechanism-Specific Reporting

• The view/lease plugin adds an openness requirement and prioritizes accepted candidates that identify a release, close, detach, or unleased resize that may revoke backing before use.The interface maps plugin methods to dependency, applicability, stability, evaluation, and live-region reasoning; Table 2 summarizes the six plugin contracts.Source: §3.4.2 · p. 8, Table 2 · p. 8
• Each candidate records acquisition, use, and event locations, relation and protection evidence, violated properties, and a transition trace; confirmed roots receive separate primary CWE labels.The evidence supports source audit and PoC design, while several manifestations may share one root.Source: §3.4.2 · p. 8
• In the view example, a release event can revoke a lease before a backing read despite the owner remaining alive; an interval export through the copy would protect that lease.A point check or a reference keeping only self alive does not provide the same interval guarantee.Source: §3.4.2 · p. 9

4. Implementation

• The 10.2K-line C++17 prototype uses Clang 14 to normalize CPython code and implements points-to analysis, call graphs, interprocedural summaries, NCDG construction, runtime-state checking, plugins, and report serialization.CMake builds two libraries and a command-line driver; the frontend parses translation units using their original compile flags.Source: §4 · p. 9
• Analysis worklists propagate effect, escape, and exposure summaries to convergence, while memory management releases frontend copies and temporary points-to results when their facts are no longer needed.The interprocedural CFG takes ownership of normalized functions before NCDG construction.Source: §4 · p. 9
• Versioned semantic catalogs provide API, macro, callback, effect, type, target, and protection records; free-threaded exposure is the default, while conventional-GIL mode requires explicit evidence.Versioned JSON reports preserve dependencies, events, graph relations, candidates, source evidence, and configuration metadata; diagnostics record witness retention and protection decisions.Source: §4 · p. 9

5. Evaluation

• The study analyzes every translation unit in the three free-threaded CPython compilation databases and audits deduplicated state-violation fingerprints.Dynamic qualification includes free-threaded builds, compatibility-GIL controls, and separately compiled conventional-GIL builds.Source: §5 · pp. 9–10

5.1. RQ1: Effectiveness on ConcurrBench

• All 180 ConcurrBench cases were classified correctly, and full state-aware analysis raises precision from 50.85% to 100% while retaining 100% recall.The benchmark tests six plugins with matched positive and negative cases; it measures conformance to intended distinctions, not general recall on unseen native code.Source: §5.1 · p. 10, Table 3 · p. 10

5.2. RQ2: Efficiency on CPython

• Every release’s analysis median is below 28 seconds and 0.8 GiB peak RSS; the flow-sensitive baseline exhausts 48 GiB without a report.Andersen’s median analysis time is 22.13–27.66 seconds, with 670–784 MiB median peak RSS; the incomplete baseline run leaves accuracy unmeasured.Source: §5.2 · p. 11, Table 4 · p. 12

5.3. RQ3: Real-Bug Detection and Confirmation

• Removing derived relation recovery loses 25–44 represented roots per release, while removing cross-entry events loses 73–94.The production ablations retain the Full dependency population in local-only mode; the bounded-witness check recovers none of these losses.Source: §5.3 · pp. 12, 14, Table 5 · p. 12
• 1,094 of 4,273 frozen fingerprints were confirmed (25.60% yield), representing 139 qualified free-threaded roots; the cross-mode inventory contains 144 roots.The inventory includes 125 native failures, 17 semantic or invariant violations, and two scheduling observations; all 34 GIL roots have conventional-build evidence.Source: §5.3 · pp. 11, 13, 14

1 Why Dependency Invalidation Helps

• Dependency invalidation can cross fields or allocations: a dictionary deletion may invalidate a later increment of its former value, without same-address instructions.Race reports focus on unordered concurrent accesses; CONCURDEP focuses on state assumed by a later native use and the event that revokes it.Source: §6 · p. 14
• A decoder callback can clear TextIOWrapper.tell’s borrowed snapshot on the same thread despite the GIL, while its object critical section excludes peer threads.The NCDG follows the callback to re-entrant seek and matches it to the snapshot dependency; per-object liveness or same-address race analysis can miss the relation and chain.Source: §6 · p. 14

2 Confirmation Yield and Specification Cost

• At 25.60% confirmation yield, production reports require source review; non-confirmed reports often lack owner facts such as pre-publication privacy or teardown exclusion.Without prospective review-time or refuted/unresolved labels, the study reports audit units and yield, not person-hours or counted false-positive causes.Source: §6 · p. 15

Catalog limitations

• Catalog omissions can cause false negatives, release changes need maintenance, and unknown idioms remain outside measured scope.The frozen catalogs contain 338–397 facts; source-equivalent inheritance reduces re-review, while extraction from C annotations and generated Clinic metadata is proposed for future work.Source: §6 · p. 15

Production capability ablation

• Derived wrapper and source inference add 3,770–4,106 dependencies and retain 25–44 represented roots; cross-entry event connection retains 73–94 roots versus local-only analysis.Direct catalog rules account for 1,904–2,134 dependencies; coarse protection preserves the represented-root set, with two source-refuted coarse-only warnings among 22 divergent decisions.Source: §6 · p. 15

3 Limitations

• Context-insensitive points-to and target abstractions can merge unrelated objects or paths, while approximate reachability retains potential invalidations at the cost of false positives.Missing contracts, acquisition patterns, or state dimensions can cause false negatives; new properties or effects require core lattice and transfer extensions.Source: §6 · p. 15

Scope and downstream use

• The prototype reports possible invalidations but does not synthesize schedules, tests, or patches; practical exploitability depends on API exposure, allocator behavior, privileges, and embedding application.The abstraction may extend to native reference, view, handle, or iterator APIs, but this evaluation covers CPython.Source: §6 · p. 15

Implementation limitations

• Analysis covers three Linux CPython snapshots and leaves inline assembly, excluded platform modules, unmodeled libraries, and uncataloged extensions opaque.Third-party extensions and other runtimes remain future evaluation; conventional-GIL reasoning depends on cataloged callback, finalizer, signal, foreign-thread, and GIL-release mechanisms.Source: §6 · pp. 15–16

Ground truth

• All 418 root–version–runtime rows have normalized technical status, and all 144 roots pass the evidence-category audit.The audit retains observation and causal material for every root and distinguishes public guarantees, internal invariants, and study-adopted correctness expectations.Source: §4 · p. 16
• Ground truth relies on manual labels and root grouping, and without full-dataset reviewer agreement, grouping, primary-CWE labels, and inheritance remain judgment-sensitive.Clean stress leaves source-valid risks open, and crashes sharing a root count once.Source: §4 · p. 16

Version and platform scope

• The three Linux/x86-64 snapshots span experimental 3.13 FT, supported baseline 3.14, and release-candidate 3.15; later source changes and platform conditions can affect manifestation.Scheduling, allocator behavior, assertions, and sanitizer availability also affect proof-of-concept outcomes; clean execution supports only that run.Source: §4 · p. 16

Comparative scope

• ConcurrBench ablations measure exposure, target/interval, and state/protection contributions, while production capability ablations report profile retention and complete-witness root representation.The external matrix measures acceptance and completion at each tool’s stated input scope; an accuracy comparison with SVF requires a shared oracle.Source: §4 · p. 16

Security impact

• Inventory failures include crashes, use-after-free or wild writes, traversal invalidation, and corrupted runtime data, threatening availability and memory integrity.Practical exploitability depends on API exposure, allocator behavior, privileges, and the embedding application; High/Critical labels prioritize mechanism-family review, not deployment severity.Source: §4 · p. 16

Ethics and disclosure

• Experiments use local builds and synthetic inputs, and the aggregate disclosure had no maintainer acknowledgment, CVE, or fix attributed to it as of September 22.The two later catalog-gap roots remain for follow-up.Source: §4 · p. 16

1 Dynamic Race and Memory-Error Detection

• Dynamic ThreadSanitizer and AddressSanitizer identify synchronization gaps or manifested memory errors, whereas CONCURDEP connects runtime acquisitions, invalidating events, and later uses statically.Dynamic tools need triggering inputs and schedules; CONCURDEP trades that requirement for false positives.Source: §7 · p. 17

2 Static Data-Race Analysis

• Static race analyses use aliasing, locksets, escape reasoning, and summaries, while CONCURDEP checks acquisition-to-use dependencies whose validity events can change across locations and runtime relations.Examples of those relations include ownership and buffer leases.Source: §7 · p. 17
• Clang Thread Safety Analysis checks annotated locking disciplines, complementing CONCURDEP’s recovery of protection from unannotated implementation code.Source: §7 · p. 17

3 Python/C Lifecycle and Interference-Aware Type-

• CPyChecker, Pungi, and PyRefcon track reference counts, affine programs, or PyObject lifecycle transitions; CONCURDEP checks relational revocation while a live owner’s subject or backing relation changes.Its scope includes containment, address, traversal, and lease obligations across parallel or re-entrant entries.Source: §3 · p. 17
• Interference-aware typestate combines transitions with inferred locksets, whereas CONCURDEP specializes in implicit CPython relations, cross-entry events, and property-specific protection.It checks existing unannotated code under its catalog and may-analysis limits.Source: §3 · p. 17

4 Testing Language Runtimes

• PyRTFuzz and UAFL expose failures along explored programs and schedules; CONCURDEP reports source-derived dependency/event chains for downstream dynamic confirmation.Schedule-aware test generation is a proposed extension.Source: §3 · p. 17

8. Conclusion

• 144 roots span free-threaded and conventional-GIL builds, including 125 with native-failure evidence and 95 without an earlier public report of the same root.The study describes dependency invalidation as a practical unit for failures crossing references, representations, callbacks, and execution modes.Source: §8 · p. 17
• All 180 controlled cases were classified correctly, and each selected release completed below 28 seconds and 0.8 GiB peak RSS in five-run medians.Frozen reports represented 139 free-threaded roots; two repaired catalog gaps yielded all 141 qualified free-threaded roots in the study corpus.Source: §8 · p. 17
• Production ablations show that derived-relation recovery and cross-entry event connection retain represented-root evidence that restricted variants lose, while witness-bound reruns preserve the semantic warning set.Source: §8 · p. 17

Appendix A. Plugin Specifications

• The five appendix plugins share an acceptance predicate, while the core supplies reachability and alias evidence and enforces common target, overlap, and protection requirements.The core computes temporal overlap, eligible may-execute context, and may-target matching; plugins select applicable dependencies and required stability properties.Source: Appendix A · p. 19
• Storage-generation and container-traversal plugins flag address revocation and stale saved bounds, positions, or entries, respectively.The storage plugin identifies resize, reallocation, rebuild, close, or free as possible revoking events.Source: Appendix A · p. 19
• Borrowed-object lifetime checks require both lifetime and relation stability until promotion or final use; uncertain use contracts can create false positives.The rationale distinguishes a still-valid acquisition relation from a subject that remains alive, and some uses require both properties.Source: Appendix A · p. 19
• The re-entry plugin links callback or event effects to possible mutation, but excludes owned or pinned borrowed-object dependencies, a known false-negative boundary for relation-changing re-entry.High-priority reports name the callback that could replace or clear retained state before native execution resumes.Source: Appendix A · p. 19

Appendix B. NCDG Scale

• Reference-drop checks receive highest review priority because dropping to zero can run destructors and reclaim the subject before its final use.Table 13 reports serialized event-aware NCDG graph-object counts for each CPython release; those counts complement time and memory results.Source: Appendix A · p. 19, Appendix B · pp. 19–20, Table 13 · p. 20

Appendix C. Focused Qualification Runs

• The qualification used three pinned revisions built with GCC 13, debug assertions, AddressSanitizer, and free threading, with a three-worker harness retaining run evidence.Table 14 summarizes 30 primary jobs and ten focused retries; SQLite and writer-stats include isolated retries.Source: Appendix C · p. 20, Table 14 · p. 20
• A clean focused stress run did not consistently exclude failures: SQLite’s primary run was clean, but four of five isolated retries aborted.OrderedDict retained conventional-GIL ASan failures from all three pinned releases despite a clean focused rerun; all six current writer-stats free-threaded executions were clean despite a prior SIGSEGV description.Source: Appendix C · p. 20

Appendix D. Aggregate Component-Coverage Summary

• Table 15 summarizes confirmed roots across 61 logical components, with separate free-threaded and conventional-GIL counts and roots deduplicated across releases and modes.The library-level collections entry and its OrderedDict implementation are consolidated as one logical component.Source: Appendix D · p. 20, Table 15 · p. 20

Appendix E. Confirmed Bug Case Studies

• Two concurrent Parse() calls on one free-threaded shared Expat parser can corrupt native state; a 3.14 ASan PoC overwrote a guard, and recursive parsing under the GIL also corrupted error state.The parser API forbids parsing through an active parser from one of its handlers; the Python wrapper serializes or rejects a second entry, but the free-threaded module permits both calls into Expat.Source: Appendix E · p. 20
• A stale inline-dictionary validity check can make __getstate__ report an impossible empty state after a peer replaces the dictionary, silently omitting security-relevant state.The PoC produced the result after 3,182 reads on 3.15 free-threaded CPython; the same binary with the GIL completed 50,000 rounds.Source: Appendix E · p. 21
• A borrowed module.__dir__ callable can be replaced after lookup and reach zero references before dispatch, producing use-after-free in both free-threaded and conventional-GIL reproductions.The free-threaded ASan build crashed in under one second; the GIL reproduction used a C callable that released the GIL inside tp_call.Source: Appendix E · p. 21
• A decoder callback can re-enter seek(0), release borrowed snapshot bytes, and leave tell() consuming reclaimed storage despite an object critical section.The PoC refilled the freed size class with Z, which FT and GIL runs then consumed through bulk and single-byte paths.Source: Appendix E · p. 21