moon-mtl

    Bounded past metric temporal logic over timestamped Boolean observations

    temporal-logic
    monitoring
    stream
    verification
    Download zip
    Author
    Version
    0.1.0
    License
    Apache-2.0
    Last updated
    3 hours ago
    Downloads
    2

    No dependencies

    #MoonMTL

    MoonMTL 用来检查带时间戳的事件日志:发送数据前是否完成握手、任务执行时租约是否仍有效、设备报告恢复前是否经过了一段稳定观测。规则可以嵌套,多个规则可以共享子表达式。

    项目实现有界过去时度量时序逻辑(Past MTL)。输入是严格递增的非负 Int64 时间戳,以及各命题在该次观测中的布尔值。核心库只依赖 MoonBit 标准库,支持 wasm、wasm-gc 和 JavaScript;文件命令行使用 Node.js。

    send -> once[1,12] handshake working -> (allowed since[0,8] renew) recovered -> historically[0,4] healthy

    第一条规则表示:观察到 send 时,必须在过去 1~12 个时间单位内观察到 handshake。时间单位由调用者统一约定。

    #运行

    本地验证环境为 MoonBit 0.10.19。Node.js 22 及以上用于命令行,Python 3 用于复现实验。

    moon check --deny-warn moon test --deny-warn moon test --target wasm-gc --deny-warn moon test --target js --deny-warn moon run --target js cmd/main scenario handshake 240 moon run --target js cmd/main scenario lease 240 moon run --target js cmd/main scenario recovery 240

    当前工具链直接在包路径后传参数。编译后的命令也可以直接调用:

    moon build --target js --release --deny-warn node _build/js/release/build/cmd/main/main.js --help node _build/js/release/build/cmd/main/main.js replay examples/rules.json examples/events.jsonl python scripts/verify_cli.py python scripts/benchmark.py python scripts/count_source.py

    rules <场景> 输出规则文档,export <场景> <数量> 输出 JSONL 日志,bench <场景> <数量> 输出基准原始记录。三个场景都包含正常与违规路径。

    #在其他 MoonBit 项目中使用

    在依赖配置中导入本模块并指定别名 @mtl。库的基本调用顺序如下:

    let plan = @mtl.Plan::from_strings([
    ("send_checked", "send -> once[1,12] handshake"),
    ]).unwrap()
    let monitor = @mtl.Monitor::new(plan)
    let observation = @mtl.Observation::new(
    0L,
    Map([("send", false), ("handshake", true)]),
    ).unwrap()
    let decision = monitor.push(observation).unwrap()
    let verdict = decision.value("send_checked")

    Plan 是可共享的编译结果;每个 Monitor 独立持有更新状态。Reference 是独立递归解释器,用于核对结果,不作为快速执行路径。Audit 统计每条规则的通过数、失败数、连续失败段和首次/末次失败位置,不保存整个日志。

    JsonlSession.feed 接收字符串块,完成一行后提交事件。feed_each 在每一行提交后立即交付判定,后续坏行不会丢掉前缀判定。finish 处理最后一个未换行的记录。每块、每条记录最多 1,048,576 个 UTF-16 代码单元。会话遇错后关闭。CLI replay 以 64 KiB 的块读取文件,逐行严格解码 UTF-8,将判定写到标准输出。

    #数据与结果校验

    事件示例:

    {"time":"9007199254740993","values":{"send":false,"handshake":true}}

    时间戳使用十进制字符串,覆盖完整非负 Int64,避免 JavaScript 的浮点整数精度问题。每次观测都必须提供计划所需的全部命题;不会把缺失命题猜成 false,也不会沿用上一条的值。重复键、未知结构字段、非布尔命题值会被拒绝。

    Decision.to_json 和 Plan.decision_from_json 支持传输结果。解码只检查结构;需要提供输入日志并调用 Plan.verify_decision 才能检查结果是否正确。Monitor.explain 返回相关节点、时间窗口、见证及 Since 的阻断位置,Plan.verify_evidence 用独立解释器校验这些片段。

    见证不是签名,也不是对现实世界完整性的证明。verify_evidence 检查片段的正确性,不保证调用者提交的片段包含完整解释。详细语义和预算见 语义说明。

    #实现与证据

    解析器把规则编译成拓扑排序 DAG,相同子表达式只计算一次。Once 保存满足条件的候选,Historically 保存反例候选,Since 在左式为假时清除旧见证。队列使用逻辑头和分段回收,避免每次移动整个数组。单条更新先检查并计算,再统一提交;时间戳、命题和候选预算错误都不会改变监测器状态。

    测试包括随机嵌套公式差分、短轨迹穷举、时序恒等式、时间平移、规则重排、长轨迹队列回收、错误后重试、传输数据拒绝和见证篡改。核心库、测试、命令行和场景代码的分项统计见 源代码统计。

    三组对照实验使用相同的确定性日志,对比共享 DAG、每条规则独立监测以及离线递归解释器。原始数据、环境和局限见 实验报告。这些是合成的应用日志,不代表真实生产部署,也没有据此声称优于 Reelay。

    本轮改进使用哈希去重、过期位置下界查找、时序提交调度和数组复用,并为规则查询建立索引。改动前后使用相同日志重新测量,见 算法优化对照。

    #范围

    目前不支持未来时运算、乱序到达、连续时间插值、任意数值谓词或自动学习协议。若应用需要“数值超过阈值”,应先在应用层生成明确的布尔命题。Previous 指上一条观测,不是上一毫秒。

    这是独立实现,算法依据时序逻辑语义和公开文献。与现有项目的关系及许可证记录见 来源说明。许可证为 Apache-2.0。

    源码仓库见 clbbbb/moon-mtl。在使用本库的 MoonBit 项目中运行 moon add clbbbb/moon-mtl@0.1.0 安装。

    Audit

    pub struct Audit {
    // private fields
    }

    Audit::explain

    fn Audit::explain(self : Audit, name : String) -> Result[Array[Evidence], MonitorError]

    Audit::last_decision

    fn Audit::last_decision(self : Audit) -> Decision?

    Audit::new

    fn Audit::new(plan : Plan) -> Audit

    Audit::push

    fn Audit::push(self : Audit, observation : Observation) -> Result[Decision, MonitorError]

    Update counters only after the monitor atomically accepts an observation. The audit retains O(number of rules) counters and no observation history.

    Audit::stats

    fn Audit::stats(self : Audit) -> MonitorStats

    Audit::summaries

    fn Audit::summaries(self : Audit) -> Array[RuleSummary]

    Audit::summary

    fn Audit::summary(self : Audit, name : String) -> RuleSummary?

    CandidateQueue

    type CandidateQueue

    Decision

    pub struct Decision {
    // private fields
    }

    Decision::all_true

    fn Decision::all_true(self : Decision) -> Bool

    Decision::names

    fn Decision::names(self : Decision) -> Array[String]

    Decision::position

    fn Decision::position(self : Decision) -> Int

    Decision::timestamp

    fn Decision::timestamp(self : Decision) -> Int64

    Decision::to_json

    fn Decision::to_json(self : Decision) -> String

    Decision::value

    fn Decision::value(self : Decision, name : String) -> Bool?

    Decision::values

    fn Decision::values(self : Decision) -> Array[Bool]

    Evidence

    pub(all) struct Evidence {
    node : Int
    kind : String
    value : Bool
    position : Int
    time : Int64
    lower_age : Int64?
    upper_age : Int64?
    witness : Witness?
    barrier : Witness?
    }

    One relevant graph evaluation. Offsets describe ages, not absolute times. An absent witness for a false Once/Since describes absence over the observed window, not proof that no unobserved real-world event occurred.

    Formula

    pub(all) enum Formula {
    Constant(Bool)
    Atom(String)
    Not(Formula)
    And(Formula, Formula)
    Or(Formula, Formula)
    Implies(Formula, Formula)
    Previous(Formula)
    Once(Interval, Formula)
    Historically(Interval, Formula)
    Since(Interval, Formula, Formula)
    }

    Pointwise past-time formulas. Since requires left at every observed position strictly after its right-hand witness, including the current position.

    Formula::format

    fn Formula::format(self : Formula, limits? : Limits) -> Result[String, MonitorError]

    Canonical syntax with precedence-aware parentheses. Validation bounds AST traversal and ensures every emitted identifier is accepted by the parser.

    Interval

    pub struct Interval {
    // private fields
    }

    Closed interval in the caller's nonnegative integer time unit.

    Interval::lower

    fn Interval::lower(self : Interval) -> Int64

    Interval::new

    fn Interval::new(lower : Int64, upper : Int64) -> Result[Interval, MonitorError]

    Interval::upper

    fn Interval::upper(self : Interval) -> Int64

    JsonlSession

    pub struct JsonlSession {
    // private fields
    }

    Chunked JSONL ingestion. A session retains only the unfinished record and monitor state. Failures seal the session: accepted prefixes cannot be accidentally replayed by retrying the same chunk.

    JsonlSession::buffered_units

    fn JsonlSession::buffered_units(self : JsonlSession) -> Int

    JsonlSession::error

    fn JsonlSession::error(self : JsonlSession) -> MonitorError?

    JsonlSession::explain

    fn JsonlSession::explain(self : JsonlSession, name : String) -> Result[Array[Evidence], MonitorError]

    JsonlSession::feed

    fn JsonlSession::feed(self : JsonlSession, chunk : String) -> Result[Array[Decision], MonitorError]

    Each chunk and unfinished record is limited to 1 MiB UTF-16 code units. Returned decisions cover completed lines only. On error, inspect stats or last_decision for the accepted prefix; the Result does not carry that prefix.

    JsonlSession::feed_each

    fn JsonlSession::feed_each(self : JsonlSession, chunk : String, emit : (Decision) -> Unit) -> Result[Unit, MonitorError]

    Deliver each accepted record before moving on to the next one. The callback must not call feed or finish on this same session.

    JsonlSession::finish

    Finish an optional non-newline-terminated last record. Calling finish twice succeeds with no extra decisions, while feed after finish is always rejected.

    JsonlSession::is_finished

    fn JsonlSession::is_finished(self : JsonlSession) -> Bool

    JsonlSession::last_decision

    fn JsonlSession::last_decision(self : JsonlSession) -> Decision?

    JsonlSession::new

    fn JsonlSession::new(plan : Plan) -> JsonlSession

    JsonlSession::stats

    Limits

    pub struct Limits {
    // private fields
    }

    Explicit ceilings bound parser, compiler, reference and live monitor work.

    Limits::defaults

    fn Limits::defaults() -> Limits

    Limits::max_candidates

    fn Limits::max_candidates(self : Limits) -> Int

    Limits::max_depth

    fn Limits::max_depth(self : Limits) -> Int

    Limits::max_events

    fn Limits::max_events(self : Limits) -> Int

    Limits::max_nodes

    fn Limits::max_nodes(self : Limits) -> Int

    Limits::new

    fn Limits::new(nodes? : Int, depth? : Int, candidates? : Int, events? : Int) -> Result[Limits, MonitorError]

    Monitor

    pub struct Monitor {
    // private fields
    }

    A monitor owns all mutable queues and prior values; plans may be shared. It stores witnesses, not the complete input trace. One push is atomic on validation or capacity errors: callers may retry the same timestamp.

    Monitor::explain

    fn Monitor::explain(self : Monitor, name : String) -> Result[Array[Evidence], MonitorError]

    Explain the most recent rule decision. Boolean branches select sufficient evidence; temporal nodes stop at the historical witness instead of wrongly explaining their child's value at the current observation.

    Monitor::last_decision

    fn Monitor::last_decision(self : Monitor) -> Decision?

    Monitor::new

    fn Monitor::new(plan : Plan) -> Monitor

    Monitor::plan

    fn Monitor::plan(self : Monitor) -> Plan

    Monitor::push

    fn Monitor::push(self : Monitor, event : Observation) -> Result[Decision, MonitorError]

    Monitor::replay_jsonl

    fn Monitor::replay_jsonl(self : Monitor, text : String) -> Result[Array[Decision], MonitorError]

    JSONL replay is transactional per record, like push. Earlier accepted records remain committed when a later line fails. A trailing newline is permitted; blank records are errors. The whole batch has a 16 MiB code-unit ceiling.

    Monitor::stats

    fn Monitor::stats(self : Monitor) -> MonitorStats

    MonitorError

    pub(all) enum MonitorError {
    InvalidInterval
    InvalidTimestamp(Int)
    MissingAtom(String, Int)
    InvalidPosition(Int)
    ResourceLimit(String)
    SyntaxError(Int, String)
    InvalidData(String)
    }

    MonitorError::message

    fn MonitorError::message(self : MonitorError) -> String

    MonitorStats

    pub(all) struct MonitorStats {
    processed : Int
    graph_nodes : Int
    retained_candidates : Int
    peak_candidates : Int
    node_updates : Int64
    }

    Node

    type Node

    Observation

    pub struct Observation {
    // private fields
    }

    Own an immutable snapshot of the caller's valuation; absent is not false.

    Observation::from_json

    fn Observation::from_json(text : String) -> Result[Observation, MonitorError]

    Timestamps are decimal strings, preserving every Int64 bit in JavaScript. Unknown fields and duplicate keys are rejected to prevent silent typos.

    Observation::new

    fn Observation::new(time : Int64, values : Map[String, Bool]) -> Result[Observation, MonitorError]

    Observation::timestamp

    fn Observation::timestamp(self : Observation) -> Int64

    Observation::to_json

    fn Observation::to_json(self : Observation) -> String

    Observation::value

    fn Observation::value(self : Observation, name : String) -> Bool?

    Plan

    pub struct Plan {
    // private fields
    }

    Immutable shared execution graph. Rule order is preserved; every child node precedes its parents, so one event needs only one topological pass.

    Plan::atom_names

    fn Plan::atom_names(self : Plan) -> Array[String]

    Plan::decision_from_json

    fn Plan::decision_from_json(self : Plan, text : String) -> Result[Decision, MonitorError]

    Decode verdicts in this plan's order. Decoding validates structure only; verify_decision checks the claim against actual observations independently.

    Plan::formula

    fn Plan::formula(self : Plan, rule : Int) -> Result[Formula, MonitorError]

    Plan::from_json

    fn Plan::from_json(text : String, limits? : Limits) -> Result[Plan, MonitorError]

    Portable rule documents carry syntax rather than internal DAG node IDs. Resource limits are supplied by the receiver, never trusted from the wire.

    Plan::from_strings

    fn Plan::from_strings(rules : Array[(String, String)], limits? : Limits) -> Result[Plan, MonitorError]

    Plan::new

    fn Plan::new(rules : Array[(String, Formula)], limits? : Limits) -> Result[Plan, MonitorError]

    Plan::node_count

    fn Plan::node_count(self : Plan) -> Int

    Plan::rule_count

    fn Plan::rule_count(self : Plan) -> Int

    Plan::rule_index

    fn Plan::rule_index(self : Plan, name : String) -> Int?

    Expected constant-time lookup without exposing mutable plan internals.

    Plan::rule_names

    fn Plan::rule_names(self : Plan) -> Array[String]

    Plan::to_json

    fn Plan::to_json(self : Plan) -> String

    Plan::validate_trace

    fn Plan::validate_trace(self : Plan, trace : Array[Observation]) -> Result[Unit, MonitorError]

    Plan::verify_decision

    fn Plan::verify_decision(self : Plan, trace : Array[Observation], decision : Decision) -> Result[Bool, MonitorError]

    Independently re-evaluate a complete decision against its input prefix. Matching verdicts says nothing about unobserved executions or authenticity.

    Plan::verify_evidence

    fn Plan::verify_evidence(self : Plan, trace : Array[Observation], evidence : Array[Evidence]) -> Result[Bool, MonitorError]

    Verify reported node values and any witness/barrier against actual records. This validates fragments, not completeness of a caller-supplied explanation.

    Reference

    pub struct Reference {
    // private fields
    }

    Validates and owns the trace array once. Each evaluate call has an explicit recursion-work ceiling; nested historical formulas cannot run unbounded.

    Reference::evaluate

    fn Reference::evaluate(self : Reference, position : Int) -> Result[Decision, MonitorError]

    Reference::last_steps

    fn Reference::last_steps(self : Reference) -> Int

    Reference::new

    fn Reference::new(plan : Plan, trace : Array[Observation], steps? : Int) -> Result[Reference, MonitorError]

    RuleSummary

    pub(all) struct RuleSummary {
    name : String
    accepted : Int
    rejected : Int
    failure_runs : Int
    current_failure_run : Int
    longest_failure_run : Int
    first_failure : Witness?
    last_failure : Witness?
    last_transition : Witness?
    latest : Bool?
    }

    Per-rule operational counters. A failure run counts consecutive observed false verdicts, not continuous elapsed-time violation duration.

    Witness

    pub(all) struct Witness {
    position : Int
    time : Int64
    }

    evaluate_reference

    fn evaluate_reference(formula : Formula, trace : Array[Observation], position : Int, steps? : Int) -> Result[Bool, MonitorError]

    Independent semantic reference: deliberately enumerates witnesses and intervening positions. It shares no execution caches with the online path.

    parse

    fn parse(text : String, limits? : Limits) -> Result[Formula, MonitorError]

    ASCII identifiers; character offsets in errors count Unicode scalar values. Precedence: unary > since > & > | > ->. Implication associates to the right.