# Pattern Synthesis + ReDoS Safety Report

> Pattern Synthesis + ReDoS Safety Report is a paid API for AI agents from s3.oddments.ai, paid per call via x402, $0.1/call, status down (last checked 2026-10-13).

Synthesizes a verified regular expression from positive/negative example strings and reports a catastrophic-backtracking (ReDoS) safety analysis

## Facts

- Endpoint: POST https://s3.oddments.ai/v1/synthesize?utm_source=zero.xyz
- Price: $0.1/call
- Payment: x402
- Status: down
- Last checked: 2026-10-13
- Activations on Zero: 0
- Tags: x402
- Canonical page: https://www.zero.xyz/c/pattern-synthesis-redos-safety-report-95014592
- Structured record (JSON): https://api.zero.xyz/v1/capabilities/cap_AJz_nIBDzyFLRrnABOZGc

Status and success rate cover calls made through Zero and Zero's own probes. Third-party monitors may report differently.

## How to call it through Zero

Zero handles the 402 payment challenge and records the run. With the Zero CLI installed (`npm i -g @zeroxyz/cli`):

```sh
zero fetch --capability pattern-synthesis-redos-safety-report-95014592 -d '<json body>'
```

Example prompt: Can you synthesize a regex for me from these positive examples — 'US-1234', 'GB-5678', 'DE-0001' — and these negative examples — 'us-1234', 'USA-12', 'AB-99999', '123-ABCD' — and include the full match matrix and a ReDoS safety report?

## When to prefer this

Prefer this endpoint when you need a regex that is provably correct against a labeled example set (not just plausible), when you need an auditable match matrix to share with reviewers, when catastrophic backtracking (ReDoS) safety is a production concern, or when you need a cryptographically signed artifact proving the synthesis result. It is superior to asking a language model for a regex directly because candidates are discarded before being returned if they fail any example, eliminating silent production failures.

## Known failure modes

- No satisfying pattern found: returns a 'no_solution' status when no regex in the restricted construct set can simultaneously accept all positives and reject all negatives
- Ambiguous or contradictory examples: positive and negative sets contain the same string, causing synthesis failure
- ReDoS analysis inconclusive: method can detect catastrophic backtracking but cannot prove absence; verdict may be 'unknown' rather than 'safe'
- Malformed input: missing or empty positive/negative arrays cause a request validation error
- Overly large example sets may exceed service limits or increase latency significantly
- Payment failure: x402 payment of 0.1 USDC not fulfilled results in 402 response before synthesis begins

## How this service works

Turn labelled examples into a verified regular expression. Positives are strings you want matched. Negatives are strings you want rejected. You get three things back. 1. A regex in a portable restricted subset. 2. THE COMPLETE MATCH MATRIX. One row per example, every one, never sampled. Each row shows expected vs observed, with the match span, so you can re-check the whole claim yourself in one line. 3. A CATASTROPHIC-BACKTRACKING ReDoS ANALYSIS. It names a concrete worst-case input class when the method finds one, and it says so explicitly when it does not. This method can find backtracking. It can never establish its absence. The pattern is not a suggestion. A candidate that does not accept every positive and reject every negative is discarded before anything is returned. That is the difference between this and asking a model for a regex that works on the three examples in the prompt and fails silently in production. WHAT YOU GET IN PRACTICE: most synthesised patterns clear the structural backtracking check. The report lists every check that ran, passes included, so a report that ran is distinguishable from one that did not. When a blow-up is found you get a concrete attack string, not a warning. Synthesis is deterministic: the same examples always yield the same pattern, which is what makes the signed receipt reproducible. When your examples admit no pattern at all, for example the same string labelled both ways, you get a PROOF of impossibility naming the conflict. TWO OUTCOMES TO KNOW ABOUT BEFORE YOU BUY. 1. If no structural pattern survives your negatives, the guaranteed fallback is a pattern listing your positive examples VERBATIM, for example ^(?:AB-1234|XY-9999)$. It matches those strings and nothing else. The response labels it literal_alternation. It is always ranked last, and more negatives are what push the synthesiser off it. 2. Rarely, no candidate separates your examples at all. Status is no_separating_pattern_found. Unlike the two impossibility proofs, this is a limit of this synthesiser, not a proof that no pattern exists. Both outcomes return HTTP 200. Both are billable. We would rather you read that here than find it on an invoice. Also returned: the ranked runners-up that also satisfy every example, checked by a static backtracking scan only, not pumped, and labelled as such. Plus the derivation and the published selection rule. Plus per-dialect usage notes for Python, JavaScript, Go and PCRE. Plus the trailing-newline anchoring trap, MEASURED IN PYTHON: behaviour in other engines is argued from the construct subset, not executed. Every response carries an Ed25519-signed reproducibility receipt over the input and output hashes. A standalone verifier is served at /verify_receipt.py. It checks the signature and recompiles the pattern with your own re to reproduce every matrix row, trusting nothing we sent. Free preview at /v1/preview: 6 positives, 6 negatives, 64 characters each. Otherwise identical: same complete matrix, same ReDoS report, same signed receipt. LIMITS: paid calls take up to 200 positives, 200 negatives, 300 examples total, 512 characters each. Hard wall-clock, CPU and memory caps apply per call, published in every response. The emitted grammar is a restricted subset: literals, character classes, non-capturing groups, alternation, greedy quantifiers. It has NO lookaround, backreferences, dot, negated classes or inline flags. If you need those, this service cannot produce them. This service does not accept or execute buyer-supplied regular expressions or code. It analyses only the patterns it generated itself. WHAT IS PROVED AND WHAT IS NOT. Read this before buying. We prove the returned pattern accepts every string you labelled positive and rejects every string you labelled negative. The match matrix is the complete evidence for that claim. One row per example, never sampled, checkable by you in one line. We do NOT prove that the pattern matches your INTENT. We see your examples. We cannot see what you meant. A pattern that satisfies every example you gave can still be wrong about the next string you have not thought of. No amount of search fixes that. So every response includes a near-miss probe report. It shows strings just outside your examples and the pattern's verdict on each, so you can inspect the generalisation we made on your behalf. The same limit applies to the ReDoS analysis. For that analysis, it is a bounded method: an enumerated static scan plus bounded empirical pumping. It can find catastrophic backtracking. It can never establish its absence. Our strongest verdict is a structural no-choice-point argument over the restricted construct set we emit, stated with its preconditions. Below that, we say 'no catastrophic backtracking found by this method'. This service never calls a pattern 'safe'. Not in a verdict. Not in a response. Not anywhere. The word 'Safety' in our name names the GENRE of document you get, a backtracking safety report. It is not a verdict about your pattern.

Operated by Oddments. Paid per call in USDC on Base via x402.

## Output

Returns a JSON object containing: (1) a synthesized regular expression in a portable restricted subset guaranteed to pass all positive and reject all negative examples, (2) a complete match matrix with one row per example showing expected vs observed result and match span, (3) a ReDoS analysis verdict (e.g. 'linear_time_by_structural_argument') with named structural checks, a worst-case input class when found, and explicit notes when none was found, and (4) a cryptographically signed receipt (Ed25519) with SHA-256 hashes of the request and response.

## Request schema (JSON Schema)

```json
{
 "type": "object",
 "$schema": "https://json-schema.org/draft/2020-12/schema",
 "required": [
  "input",
  "output"
 ],
 "properties": {
  "input": {
   "type": "object",
   "required": [
    "type",
    "method",
    "bodyType",
    "body"
   ],
   "properties": {
    "body": {
     "type": "object"
    },
    "type": {
     "const": "http"
    },
    "method": {
     "const": "POST"
    },
    "bodyType": {
     "const": "json"
    }
   },
   "additionalProperties": false
  },
  "output": {
   "type": "object",
   "required": [
    "type"
   ],
   "properties": {
    "type": {
     "const": "json"
    },
    "example": {
     "type": "object"
    }
   }
  },
  "schemaReference": {
   "type": "object",
   "required": [
    "url",
    "input",
    "output"
   ],
   "properties": {
    "url": {
     "type": "string"
    },
    "input": {
     "type": "string"
    },
    "output": {
     "type": "string"
    }
   },
   "additionalProperties": false
  }
 }
}
```

## Response schema (JSON Schema)

```json
{
 "type": "json",
 "example": {
  "redos": {
   "verdict": "linear_time_by_structural_argument",
   "applied_as": {
    "match_mode": "fullmatch",
    "case_insensitive": false,
    "why_this_matters": "Both change which claims are true. Under `search` the engine restarts at every offset, so even a pattern with no ambiguity costs O(n) restarts x O(n) work and the structural linear-time verdict is NOT issued. Under `case_insensitive`, character classes are folded before any disjointness argument is evaluated, because [a-z] and [A-Z] are disjoint as text and identical to the engine.",
    "operation_measured": "re.fullmatch"
   },
   "method_limits": [
    "… the full list of 8 limits is in every response …"
   ],
   "verdict_meaning": "Under ANCHORED (fullmatch) application, the pattern's structure leaves a backtracking engine no ambiguous choice to explore, so the work it does is linear in the input length. Greedy quantifiers still create backtrack points; disjointness is what makes each retry fail in constant time. This is the strongest verdict this service issues, and it is a structural argument over a restricted construct set, not a machine-checked proof. It says nothing about `search` application, which restarts at every offset.",
   "structural_checks": [
    {
     "check": "nested_variable_quantifier",
     "result": "pass",
     "severity_if_violated": "exponential"
    },
    {
     "check": "nullable_quantifier_body",
     "result": "pass",
     "severity_if_violated": "exponential"
    },
    {
     "…": "2 further checks, passes included"
    }
   ],
   "worst_case_input_class": null,
   "no_worst_case_found_note": "No worst-case input class is reported because this method did not find one. That is not the same as there being none -- this method can find catastrophic backtracking and can never establish its absence."
  },
  "engine": {
   "python": "3.12.3",
   "service": "oddments-s3",
   "version": "1.0.0",
   "redos_method": "static ambiguity scan (re-parsed from the emitted pattern) + bounded empirical pumping, v1",
   "regex_engine": "CPython stdlib `re` 2.2.1",
   "verification": "re.fullmatch (strictest anchoring; see dialect_notes)",
   "synthesis_algorithm": "segment-profile generalisation + filtered candidate ranking, v1"
  },
  "status": "solved",
  "pattern": "^(?:[A-Z]{2}-[0-9]{4})$",
  "receipt": {
   "_note": "the real response carries a signed receipt here; these are FIELD DESCRIPTIONS, not values from a real call",
   "algorit
… (truncated)
```

## More

- Live health (JSON, refreshed every minute): https://www.zero.xyz/c/pattern-synthesis-redos-safety-report-95014592/health.json
- [Zero catalog index](https://www.zero.xyz/llms.txt)
- [Other services from s3.oddments.ai](https://www.zero.xyz/host/s3.oddments.ai/llms.txt)