{"id":"a130dbe7-bb1c-49ab-b2cf-cdab00814d23","arxiv_id":"2501.14555","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"An ASP-based encoding of provenance graphs for cyber threat detection is proposed, but the evaluation is incomplete and the scalability claims are contradicted by the reported timing table.","lead":"This paper encodes system activity graphs as logic programs in Answer Set Programming to detect attacks like data exfiltration and privilege escalation. The authors test their rules on synthetic graphs, but do not ship the data or code and report conflicting performance numbers.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The scalability evidence in Table 1 is internally contradictory and the printed ASP rules cannot be executed as given, so the central claim of a demonstrated scalable model is unsupported.","rationale":"Reader's verdict is REJECT, and the strongest claim is as stated. I agree with the direction but locate the load-bearing failure slightly differently. The reader's weakest_assumption is that the supplied rules are incomplete or use undefined predicates. That is serious, but the more decisive problem is that even if those predicates were filled in, the Table 1 numbers cannot support the claimed sub-linear scalability, and the 100k-node numbers in §4.3–4.4 contradict the table's size range. This is an internal inconsistency, not just a difference from community norms. The paper explicitly concedes in §5.2 a risk of state-space explosion on highly interconnected graphs, which further undercuts the unqualified scalability claim. A concrete reproducibility test would settle the issue: if the authors can provide a working artifact and corrected timings, the empirical part could be salvaged; as written, it cannot. No ad hominem is intended; the critique concerns evidence and internal consistency only.","tokens_in":9911,"tokens_out":3716,"duration_ms":31791,"concrete_test":"Ask the authors for the exact s(CASP) program and the synthetic-data generator, then independently run the printed queries from §4.3 and §4.4 at the sizes in Table 1 and at 100,000 nodes. The decisive check is whether multi_stage_attack/4 and anomalous_process/1 execute without unresolved predicates, and whether the measured times reproduce Table 1 and the §4.3/§4.4 100k-node claims. If the published rule set fails before answering (e.g., on reachable/3 or threshold arity), the reported evaluation cannot be reproduced.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim—that the model demonstrably handles large-scale provenance graphs with sub-linear query times—rests on §4.5/Table 1 and the case-study queries in §4.3–4.4. This evidence fails on its own terms. Table 1 gives anomaly detection as 21 ms at 1,000 nodes and 1,302 ms at 10,000 nodes; that is roughly a 62× slowdown for a 10× data increase, not sub-linear. It also reports multi-stage as 0.22 ms at 1,000 and 0.26 ms at 10,000 nodes, while §4.3 separately reports 0.259 ms for a 100,000-node dataset absent from Table 1, and §4.4 reports 1,302 ms for a 100,000-node anomaly query. The printed rules cannot be the ones that produced these numbers: attack_path/3 calls reachable/3 though only reachable/2 is defined; privilege_escalation/2 needs process_privilege/2 facts never supplied; generate_alert uses accessed_file/2 with no derivation; and the anomaly rules mix threshold/2 (§4.4) with the threshold/1 used in §3.3 and rely on findall/length, constructs not defined in the paper's ASP semantics. The data comes from an unreleased custom Python generator, with no baseline, no raw outputs, and no artifact. Thus the core assertion is unverifiable from the manuscript.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":10240,"tokens_out":3410,"duration_ms":32154,"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":[{"comment":"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.","section":"§4.5, Table 1"},{"comment":"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.","section":"§3.3 and §4.4"},{"comment":"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.","section":"§4.1 and §4.4"}],"minor_comments":[{"comment":"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.","section":"§4.3"},{"comment":"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.","section":"§2.1"},{"comment":"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.","section":"§4.2"},{"comment":"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.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":"The manuscript lacks an artifact and the evaluation data are private, which is a serious reproducibility problem for a cybersecurity venue. The internal contradictions in Table 1 and the non-executable rule listings are not cosmetic; they undermine the paper's main empirical claim. If the authors resubmit, they would need to provide complete executable ASP programs, release the data generator, and rerun the evaluation against at least one baseline, reporting standard error metrics. I do not see how these issues can be repaired within the scope of the current submission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nThe 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.\n\nThe 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.","headline":"Readable ASP rules for provenance queries, but the evaluation contradicts the scalability claim and the printed rules are not executable; desk-reject as is.","tokens_in":10699,"tokens_out":3903,"would_cite":false,"duration_ms":34455,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["answer set programming","provenance graphs","cyber threat detection","attack path tracing","data exfiltration detection","privilege escalation","anomaly detection","declarative reasoning"],"falsifier":"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.","tokens_in":9733,"feed_emoji":"🔍","tokens_out":10146,"duration_ms":85688,"temperature":0.7,"pith_summary":"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.","feed_headline":"Provenance graphs as logic programs catch multi-stage attacks","feed_subtitle":"Declarative rules over system activity graphs catch exfiltration, privilege escalation, and anomalies.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines provenance graphs and their role in cybersecurity, the object the paper models.","marker":"[13]"},{"why":"Gives the stable-model semantics on which the ASP representation and answer sets rest.","marker":"[14]"},{"why":"Surveys provenance-based intrusion detection and motivates the need for more expressive queries.","marker":"[22]"},{"why":"Identifies opportunities and challenges in provenance-based intrusion detection that the approach targets.","marker":"[9]"},{"why":"Supplies provenance data attributes and benchmark context used for realistic system-entity and edge modeling.","marker":"[17]"},{"why":"Prior application of ASP to detecting attack patterns, supporting the feasibility of ASP for security analysis.","marker":"[18]"},{"why":"Prior ASP-based security policy analysis, supporting the expressiveness and policy-enforcement claims.","marker":"[15]"}],"fun_headline_variants":["ASP turns provenance graphs into logic for threat hunting","Answer Set Programming models cyber attacks as logic rules","Logic programs catch exfiltration from system activity graphs","Provenance graphs as ASP: flexible threat detection and forensics"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["ASP turns provenance graphs into logic for threat hunting","Answer Set Programming models cyber attacks as logic rules","Logic programs catch exfiltration from system activity graphs","Provenance graphs as ASP: flexible threat detection and forensics"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00016,"raw_usage":{"total_tokens":1216,"prompt_tokens":914,"completion_tokens":302,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":530,"completion_tokens_details":{"reasoning_tokens":238}},"tokens_in":530,"tokens_out":302,"duration_ms":3187,"temperature":1.0,"reasoning_tokens":238,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T15:01:48.907733+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"In: The Logic Programming Paradigm, pp","cited_arxiv_id":null,"evidence_quote":"Gives the stable-model semantics on which the ASP representation and answer sets rest."},{"cited_title":"Comp uters & Security 106 (2021)","cited_arxiv_id":null,"evidence_quote":"Defines provenance graphs and their role in cybersecurity, the object the paper models."},{"cited_title":"ACM Computing Surveys 55(7), 1–36 (2022)","cited_arxiv_id":null,"evidence_quote":"Surveys provenance-based intrusion detection and motivates the need for more expressive queries."},{"cited_title":"In: 10th USENIX Workshop on the The ory and Practice of Provenance (2018)","cited_arxiv_id":null,"evidence_quote":"Identifies opportunities and challenges in provenance-based intrusion detection that the approach targets."},{"cited_title":"International Journal of Networked and Distribute d Computing 11(2), 112– 123 (2023)","cited_arxiv_id":null,"evidence_quote":"Supplies provenance data attributes and benchmark context used for realistic system-entity and edge modeling."},{"cited_title":"In: Europea n Conference on Artificial Intelligence, pp","cited_arxiv_id":null,"evidence_quote":"Prior application of ASP to detecting attack patterns, supporting the feasibility of ASP for security analysis."},{"cited_title":"Internationa l Journal of Information Security 18, 465–479 (2019)","cited_arxiv_id":null,"evidence_quote":"Prior ASP-based security policy analysis, supporting the expressiveness and policy-enforcement claims."}],"review_version":1}