Exploring Answer Set Programming for Provenance Graph-Based Cyber Threat Detection: A Novel Approach

Fang Li; Fei Zuo; Gopal Gupta

REVIEW 3 major objections 4 minor 22 references

Exploring Answer Set Programming for Provenance Graph-Based Cyber Threat Detection: A Novel Approach

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper argues that representing provenance graphs as Answer Set Programs yields a flexible, explainable framework for cyber-threat queries such as attack-path tracing, data-exfiltration detection, and anomaly identification.

desk verdict Readable ASP rules for provenance queries, but the evaluation contradicts the scalability claim and the printed rules are not executable; desk-reject as is. read the letter →

arxiv 2501.14555 v1 pith:LCN3D3TL submitted 2025-01-24 cs.CR cs.PL

Fang Li , Fei Zuo , Gopal Gupta This is my paper · ORCID

classification cs.CRcs.PL

keywords answersetprogrammingprovenancegraphscyberthreatdetectionattackpathtracingdataexfiltrationprivilegeescalationanomalydeclarativereasoning

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper attempts to establish that Answer Set Programming (ASP) is a workable substrate for provenance-graph analysis in cybersecurity: instead of hand-coding graph traversals, an analyst writes declarative rules over the graph's nodes and labeled, timestamped edges, and the ASP solver's answer sets are the detected threats. The authors argue this yields expressiveness for complex multi-stage attacks, easy extension when new threat patterns appear, and explainable conclusions because each alert is backed by the rules that fired. They demonstrate the approach on synthetic provenance graphs with injected attacks, covering attack-path tracing, data exfiltration, privilege escalation, root-cause analysis, policy enforcement, anomaly detection, and what-if analysis, and they report query times they interpret as scalable. The paper itself notes the risks of state-space explosion on very large graphs and the need for logic-programming expertise to author the rules.

What carries the argument

The load-bearing object is the ASP program itself, built in layers. Facts encode the provenance graph (entity types and edge(From,To,Type,Timestamp)); core rules define reachable/2, before/2, and causal_dependency/2; advanced rules add attack_path with a depth bound, data_exfiltration by correlating read and send_data edges with timestamps, privilege_escalation by comparing process privilege levels, root_cause by finding causally earliest compromised events, alert_generation with a not authorized_process default-negation test, and anomalous_process using aggregate object counts and thresholds. The engine that carries the argument is stable-model semantics: negation-as-failure lets rules say 'unless there is evidence to the contrary,' which is how alerts and policy violations become answer sets.

What would settle it

A direct reproducibility check is to run the printed rule set on the supplied synthetic graph and ask for multi_stage_attack; because predicates such as reachable/3, process_privilege/2, accessed_file/2, and threshold/2 are never defined, the program cannot be grounded as printed, which would settle whether the reported query outputs are reproducible. For the scalability claim, measuring average query time at 1,000, 10,000, and 100,000 nodes on the same solver and hardware would show whether times grow sub-linearly; the paper's own anomaly-detection figures (21 ms at 1,000, 1,302 ms at 10,000) already grow faster than linear.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that provenance graphs can be lifted into a logic program whose stable models are threat-detection results. Nodes become facts (process, file, network_connection, user, memory_object), edges become edge(From, To, Type, Timestamp) facts, and a layered rule set derives reachability, temporal order, and causal dependency before composing them into higher-level predicates such as attack_path, data_exfiltration, privilege_escalation, root_cause, generate_alert, policy_violation, anomalous_process, and potential_compromise. The semantics of ASP makes the inference non-monotonic: a rule like generate_alert can say that a process is unauthorized unless another rule proves it authorized, so absence of evidence is treated as a real fact. The reported case studies find all injected multi-stage attacks and anomalous processes, and the paper interprets the measured query times as evidence that the approach scales to large graphs.

Load-bearing premise

The load-bearing premise is that the published ASP rules are complete and executable, but the rule set in the paper invokes predicates that are never defined (reachable/3, process_privilege/2, accessed_file/2, threshold/2), so the reported detections cannot be reproduced from the printed programs alone; the evaluation also assumes synthetic graphs behave like real provenance data.

Editorial extensions

If this is right

New threat patterns can be added as declarative rules without rewriting the graph representation, shortening development time for new analysis types.
The same fact base serves both real-time query-style detection and post-incident forensic reconstruction, because analysis is driven by queries over a static representation.
Every alert is explainable by construction: the chain of facts and rules that entails the answer set can be inspected, supporting auditing and policy validation.
Policy enforcement and anomaly detection can be expressed as constraints plus default negation, allowing the system to flag violations without enumerating every bad behavior.
If the reported sub-linear query-time trend holds, focused path queries on large provenance graphs become practical without full-graph scans.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural next step, implicit in the design, is to pair the fact layer with temporal ASP or weighted rules so queries can enforce explicit time windows—slow, multi-week intrusions are the case the current examples approximate but do not bound.
The same human-readable rule layer could be used as a living security-policy document, since the rules that raise alerts are exactly the conditions an auditor would want to inspect.
A stronger evaluation than the paper reports would run these rules against real labeled provenance traces with ground-truth attack stages and measure precision and recall against existing provenance-based detectors.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: the paper is an exploratory application of ASP to provenance graphs. The rule encodings are clear and readable. The evaluation, however, doesn't support the claims, and the scalability statement is contradicted by the paper's own table. I would not send this out for peer review as is.

What is actually new: prior ASP security work by Sterlicchio and Rezvani focused on network attack patterns and XACML policies; encoding provenance graph facts and analysis rules (reachability, causal dependency, attack path, data exfiltration, privilege escalation, anomaly) in ASP is a reasonable new application. It is not a new technique, but the rule set in Section 3 is genuinely readable, and choosing s(CASP) for query-style analysis is sensible. The paper earns credit for showing how declarative rules express these security patterns concisely.

The soft spots are load-bearing rather than cosmetic. First, the printed rules cannot be the ones that produced the results. attack_path/3 calls reachable/3 but only reachable/2 is defined; privilege_escalation references process_privilege/2 facts that are never supplied; generate_alert uses accessed_file/2 with no derivation; and the anomaly rules in §4.4 use threshold/2 plus findall/length, which are not standard ASP constructs. As printed, the queries are not executable. Second, Table 1 is internally inconsistent: anomaly detection goes from 21 ms at 1,000 nodes to 1,302 ms at 10,000 nodes, a ~62x slowdown for a 10x dataset, and the same number 1,302 ms appears for 100,000 nodes in §4.4, while §4.3 reports 0.259 ms for 100,000. That is not sub-linear scaling by any reading. Third, the synthetic data generator is unreleased and injects attacks using the same predicates the rules match, so detection is guaranteed by construction. There is no baseline, no error metric, no stated threshold.

The representational idea is plausible—ASP is a reasonable fit for provenance queries—but the paper as written does not demonstrate it. It reads like a position piece with a sketch of an evaluation. Readers interested in declarative security analysis might skim the rules; nobody should rely on the performance numbers. If the authors fixed the rule set, shipped the data generator, and reported honest timings against a baseline, this could become a solid workshop paper. As it stands, I'd desk-reject rather than spend referee time on it.

Referee Report

3 major / 4 minor

Summary. The paper proposes encoding provenance graphs as Answer Set Programming (ASP) facts and rules, and demonstrates attack path tracing, data exfiltration detection, privilege escalation detection, root cause analysis, alert generation, and anomaly detection using the s(CASP) solver. The authors report case studies on synthetic graphs generated by an unreleased custom Python script, with execution times for multi-stage attack detection and anomaly detection on datasets from 1,000 to 10,000 nodes, and claim that query times increase sub-linearly with dataset size. The central claim is that the approach is expressive, extensible, and scalable for large-scale provenance graph analysis.

Significance. If the central claim were established, ASP-based provenance analysis would be a useful addition to the cybersecurity toolkit, offering explainable rules and flexible extension. The paper does provide a coherent conceptual encoding of several security analyses, and the idea of using a top-down ASP solver for query-style provenance reasoning is worth exploring. However, the paper does not ship an artifact, the synthetic data is unreleased, no baseline comparison is provided, and the experimental evidence is internally contradictory. As presented, the contribution is a rule-set proposal whose effectiveness and scalability are not supported by the reported data.

major comments (3)

[§4.5, Table 1] The scalability claim is contradicted by the paper's own table. Anomaly detection rises from 21 ms at 1,000 nodes to 1,302 ms at 10,000 nodes, a factor of about 62 for a factor of 10 in data size, which is not sub-linear growth. The multi-stage query times of 0.22 ms and 0.26 ms provide only two data points and do not establish any scaling trend. Additionally, §4.3 reports 0.259 ms for a 100,000-node dataset and §4.4 reports 1,302 ms for a 100,000-node dataset, while Table 1 attributes 0.26 ms and 1,302 ms to a 10,000-node dataset; these internal inconsistencies make the evaluation unusable.
[§3.3 and §4.4] The published ASP rules are not executable as printed. attack_path(X,Y,D) calls reachable(X,Y,D), but only reachable/2 is defined. privilege_escalation requires process_privilege/2 facts that are never introduced in the graph representation. generate_alert uses accessed_file/2 with no defining rule. The anomaly detection rules in §3.3 use threshold(Threshold), while §4.4 uses threshold(FileThreshold, NetThreshold), and no threshold facts are provided. As a result, the reported query outputs cannot be reproduced from the manuscript, and the model cannot be independently checked.
[§4.1 and §4.4] The validation is not convincing. The synthetic generator injects attacks as instances of the same edge predicates that the ASP rules match, such as edge(Process, File, read, T1) and edge(Process, Connection, send_data, T2), so the case studies largely verify that the rules fire on the generator's own input conventions. No real provenance benchmark is used, the generator is not released, no baseline detector or query engine is compared, and no precision, recall, or error rates are reported despite the claim of high accuracy. The phrase 'demonstrated the effectiveness' in the conclusion is therefore unsupported.

minor comments (4)

[§4.3] The query ?- multi_stage_attack(Ip, Ep, Ef, Ep) reuses the variable Ep for both the escalated process and the exit point, which imposes an unintended equality constraint; the fourth argument should presumably be a distinct variable such as Exit.
[§2.1] The statement that provenance graphs are 'acyclic in most cases' is questionable, since real system activity frequently produces cycles such as a process reading and then writing the same file; the paper should either justify this claim or acknowledge cycles explicitly.
[§4.2] The experimental setup does not report the s(CASP) version, the exact command-line options, the number of runs, or the variance of the timing measurements, so the reported averages cannot be assessed.
[Throughout] The displayed ASP code contains spacing artifacts, for example 'net work_ con n ect ion' and 'an omalou s_ p rocess', which make the listings hard to read; the final version should use monospaced, unbroken code listings.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation is demonstrated: the representational claims rest on standard ASP semantics, and the reported evaluation problems are reproducibility/consistency issues rather than equivalence-by-construction.

full rationale

The paper's central claims are empirical and representational: that provenance graphs can be encoded in ASP, and that the resulting queries exhibit scalability. Neither claim is derived by fitting a parameter to the outcome it is supposed to predict. The encoding uses standard ASP rules for reachability, temporal order, causal dependency, attack paths, exfiltration, escalation, and anomaly detection; its correctness is grounded in the s(CASP)/ASP semantics cited from the literature, not in a self-citation chain. The evaluation, however, is weak: the synthetic data generator is not released, threshold/2 facts are never supplied, attack_path/3 calls reachable/3 while only reachable/2 is defined, and Table 1 contradicts the 'sub-linear' scalability claim (anomaly detection goes from 21 ms at 1,000 nodes to 1302 ms at 10,000 nodes, a roughly 60x slowdown for 10x data, while the multi-stage figures conflict with the 100,000-node timings reported in Sections 4.3 and 4.4). These are reproducibility and correctness concerns, not circularity: the detection 'successes' on authored synthetic scenarios are at most a self-consistency check rather than independent validation, but the manuscript does not exhibit any equation, fitted parameter, or theorem that reduces the claimed results to their inputs by construction. Self-citations to the s(CASP) solver and to a provenance benchmark are present but are not the load-bearing justification for the paper's conclusions. Accordingly, no circular step is demonstrable from the text.

Assumptions & free parameters 2 free parameters · 2 assumptions · 0 invented entities

The central claims rest on standard ASP semantics plus two domain assumptions: the s(CASP) solver behaves correctly, and synthetic graphs stand in for real system activity. The anomaly threshold and path-depth limit are free parameters that are never justified, and the evaluation does not validate them.

free parameters (2)

anomaly thresholds (FileThreshold, NetThreshold)
Section 4.4 anomaly detection rules rely on threshold(FileThreshold, NetThreshold) facts but the paper never states the values or how they were chosen; the detector's output is directly controlled by this parameter.
attack path depth limit (D <= 10) = 10
Section 3.3 attack_path rule restricts to paths of length at most 10; this cutoff is chosen by hand and not justified.

assumptions (2)

domain assumption s(CASP) correctly implements ASP stable-model semantics, so the printed rules are meaningful queries.
The paper relies on the solver's correctness for all reported results (Section 3).
ad hoc to paper The synthetic provenance graphs generated by the custom Python script represent realistic system activity and attacks.
Section 4.1 describes the generator but provides no validation or release, so the case-study conclusions assume these graphs are representative.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Exploring Answer Set Programming for Provenance Graph-Based Cyber Threat Detection: A Novel Approach." pith.science (2026). https://pith.science/paper/LCN3D3TL

@misc{pith2026250114555,
  author       = {Pith},
  title        = {Pith review of: Exploring Answer Set Programming for Provenance Graph-Based Cyber Threat Detection: A Novel Approach},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LCN3D3TL}},
  note         = {Machine review of arXiv:2501.14555}
}

read the original abstract

Provenance graphs are useful and powerful tools for representing system-level activities in cybersecurity; however, existing approaches often struggle with complex queries and flexible reasoning. This paper presents a novel approach using Answer Set Programming (ASP) to model and analyze provenance graphs. We introduce an ASP-based representation that captures intricate relationships between system entities, including temporal and causal dependencies. Our model enables sophisticated analysis capabilities such as attack path tracing, data exfiltration detection, and anomaly identification. The declarative nature of ASP allows for concise expression of complex security patterns and policies, facilitating both real-time threat detection and forensic analysis. We demonstrate our approach's effectiveness through case studies showcasing its threat detection capabilities. Experimental results illustrate the model's ability to handle large-scale provenance graphs while providing expressive querying. The model's extensibility allows for incorporation of new system behaviors and security rules, adapting to evolving cyber threats. This work contributes a powerful, flexible, and explainable framework for reasoning about system behaviors and security incidents, advancing the development of effective threat detection and forensic investigation tools.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 21 canonical work pages

[1]

Abiteboul, S., Hull, R., Vianu, V.: Foundations of databa ses, vol. 8. Addison- Wesley Reading (1995)

work page 1995
[2]

Künstl Intell 32, 177–179 (2018)

Adrian, W., Alviano, M., Calimeri, F., Others: The ASP sys tem DL V: Advance- ments and applications. Künstl Intell 32, 177–179 (2018)

work page 2018
[3]

Theory and Practice of Logic Pr ogramming 18(3-4), 337–354 (2018)

Arias, J., Carro, M., Salazar, E., Marple, K., Gupta, G.: C onstraint answer set pro- gramming without grounding. Theory and Practice of Logic Pr ogramming 18(3-4), 337–354 (2018)

work page 2018
[4]

Cambridge University Press (2003)

Baral, C.: Knowledge representation, reasoning and decl arative problem solving. Cambridge University Press (2003)

work page 2003
[5]

Theory and Practice of Logic Programming 23(1), 226–298 (2023)

Cao Tran, S., Pontelli, E., Balduccini, M., Schaub, T.: An swer set planning: A survey. Theory and Practice of Logic Programming 23(1), 226–298 (2023)

work page 2023
[6]

Dal Palù, A., Dovier, A., Formisano, A., Pontelli, E.: Exp loring life: answer set pro- gramming in bioinformatics, pp. 359–412. Association for C omputing Machinery and Morgan & Claypool (2018)

work page 2018
[7]

arXiv preprint arXiv:1405.3694 (2014)

Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Cling o= asp+ control. arXiv preprint arXiv:1405.3694 (2014)

arXiv 2014
[8]

Cambridge University Press (2014)

Gelfond, M., Kahl, Y.: Knowledge representation, reason ing, and the design of intelligent agents: The answer-set programming approach. Cambridge University Press (2014)

work page 2014

Show all 22 references

[9]

In: 10th USENIX Workshop on the The ory and Practice of Provenance (2018)

Han, X., Pasquier, T., Seltzer, M.: Provenance-based int rusion detection: oppor- tunities and challenges. In: 10th USENIX Workshop on the The ory and Practice of Provenance (2018)

2018
[10]

In: IEEE Symposium on Secur ity and Privacy

Hassan, W.U., Bates, A., Marino, D.: Tactical provenanc e analysis for endpoint detection and response systems. In: IEEE Symposium on Secur ity and Privacy. pp. 1172–1189. IEEE (2020)

2020
[11]

IEEE Transactions on Information Foren sics and Security 16, 4363–4376 (2021)

Irshad, H., Ciocarlie, G., Gehani, A., Yegneswaran, V., Lee, K.H., Patel, J., Jha, S., Kwon, Y., Xu, D., Zhang, X.: Trace: Enterprise-wide provena nce tracking for real- time APT detection. IEEE Transactions on Information Foren sics and Security 16, 4363–4376 (2021)

2021
[12]

In: 9th USENIX Workshop on the Theo ry and Practice of Provenance (2017) Exploring ASP for Provenance Graph-Based Cyber Threat Dete ction 15

Jenkinson, G., Carata, L., Bytheway, T., Sohan, R., Wats on, R.N., Anderson, J., Kidney, B., Strnad, A., Thomas, A., Neville-Neil, G.: Apply ing provenance in APT monitoring and analysis: Practical challenges for scalabl e, eﬃcient and trustworthy distributed provenance. In: 9...

2017
[13]

Comp uters & Security 106 (2021)

Li, Z., Chen, Q.A., Yang, R., Chen, Y., Ruan, W.: Threat de tection and investi- gation with system-level provenance graphs: A survey. Comp uters & Security 106 (2021)

2021
[14]

In: The Logic Programming Paradigm, pp

Marek, V.W., Truszczyński, M.: Stable models and an alte rnative logic program- ming paradigm. In: The Logic Programming Paradigm, pp. 375– 398. Springer (1999)

1999
[15]

Internationa l Journal of Information Security 18, 465–479 (2019)

Rezvani, M., Rajaratnam, D., Ignjatovic, A., Pagnucco, M., Jha, S.: Analyzing xacml policies using answer set programming. Internationa l Journal of Information Security 18, 465–479 (2019)

2019
[16]

In: International Conference on Logic Programming

Schaub, T., Thiele, S.: Metabolic network expansion wit h answer set programming. In: International Conference on Logic Programming. pp. 312 –326. Springer (2009)

2009
[17]

International Journal of Networked and Distribute d Computing 11(2), 112– 123 (2023)

Shrestha, M., Kim, Y., Oh, J., Rhee, J., Choe, Y.R., Zuo, F ., Park, M., Qian, G.: Provsec: Open cybersecurity system provenance analysis be nchmark dataset with labels. International Journal of Networked and Distribute d Computing 11(2), 112– 123 (2023)

2023
[18]

In: Europea n Conference on Artiﬁcial Intelligence, pp

Sterlicchio, G., Lisi, F.A.: Detecting patterns of atta cks to network security in urban air mobility with answer set programming. In: Europea n Conference on Artiﬁcial Intelligence, pp. 1285–1292. IOS Press (2024)

2024
[19]

In: Nordic Conference on Secure IT S ystems

Tabiban, A., Zhao, H., Jarraya, Y., Pourzandi, M., Wang, L.: Vincidecoder: Au- tomatically interpreting provenance graphs into textual f orensic reports with ap- plication to openstack. In: Nordic Conference on Secure IT S ystems. pp. 346–367. Springer International Publishing (2022)

2022
[20]

IEEE Transactions on Knowledge and Data Engineering (2024)

Wang, Z., Zhou, Y., Liu, H., Qiu, J., Fang, B., Tian, Z.: Th reatinsight: Innovating early threat detection through threat-intelligence-driv en analysis and attribution. IEEE Transactions on Knowledge and Data Engineering (2024)

2024
[21]

Digital Investigation 26, 19–28 (2018)

Xie, Y., Feng, D., Liao, X., Qin, L.: Eﬃcient monitoring a nd forensic analysis via accurate network-attached provenance collection with min imal storage overhead. Digital Investigation 26, 19–28 (2018)

2018
[22]

ACM Computing Surveys 55(7), 1–36 (2022)

Zipperle, M., Gottwalt, F., Chang, E., Dillon, T.: Prove nance-based intrusion de- tection systems: A survey. ACM Computing Surveys 55(7), 1–36 (2022)

2022

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [1]

Abiteboul, S., Hull, R., Vianu, V.: Foundations of databa ses, vol. 8. Addison- Wesley Reading (1995)

work page 1995

[2] [2]

Künstl Intell 32, 177–179 (2018)

Adrian, W., Alviano, M., Calimeri, F., Others: The ASP sys tem DL V: Advance- ments and applications. Künstl Intell 32, 177–179 (2018)

work page 2018

[3] [3]

Theory and Practice of Logic Pr ogramming 18(3-4), 337–354 (2018)

Arias, J., Carro, M., Salazar, E., Marple, K., Gupta, G.: C onstraint answer set pro- gramming without grounding. Theory and Practice of Logic Pr ogramming 18(3-4), 337–354 (2018)

work page 2018

[4] [4]

Cambridge University Press (2003)

Baral, C.: Knowledge representation, reasoning and decl arative problem solving. Cambridge University Press (2003)

work page 2003

[5] [5]

Theory and Practice of Logic Programming 23(1), 226–298 (2023)

Cao Tran, S., Pontelli, E., Balduccini, M., Schaub, T.: An swer set planning: A survey. Theory and Practice of Logic Programming 23(1), 226–298 (2023)

work page 2023

[6] [6]

Dal Palù, A., Dovier, A., Formisano, A., Pontelli, E.: Exp loring life: answer set pro- gramming in bioinformatics, pp. 359–412. Association for C omputing Machinery and Morgan & Claypool (2018)

work page 2018

[7] [7]

arXiv preprint arXiv:1405.3694 (2014)

Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Cling o= asp+ control. arXiv preprint arXiv:1405.3694 (2014)

arXiv 2014

[8] [8]

Cambridge University Press (2014)

Gelfond, M., Kahl, Y.: Knowledge representation, reason ing, and the design of intelligent agents: The answer-set programming approach. Cambridge University Press (2014)

work page 2014