{"uid":"cap_yXk3tEenDXzfT0IqBwdOV","slug":"pattern-synthesis-redos-safety-report-c9bfba8c","name":"Pattern Synthesis + ReDoS Safety Report","description":"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.\n\nOperated by Oddments. Paid per call in USDC on Base via x402.","url":"https://oddments-s3.exe.xyz/v1/synthesize","method":"POST","headers":{},"bodySchema":{"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}}},"responseSchema":{"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","algorithm":"Ed25519","input_sha256":"sha256 of your canonicalized request","output_sha256":"sha256 of this response with 'receipt' removed","signature_b64":"Ed25519 signature over the canonical signed_fields","receipt_version":"oddments-receipt/1"},"alternatives":[{"pattern":"^(?:(?:AB|QQ|XY|ZZ)-(?:0001|1234|4242|9999))$","strategy":"segment_profile","satisfies_all_examples":true,"redos_verdict_static_only":"static scan only (not pumped): no ambiguity construct found, and the no-ambiguous-choice-point argument holds for anchored application"},{"pattern":"^(?:[\\-012349ABQXYZ]{7,})$","strategy":"whole_string_class","satisfies_all_examples":true,"redos_verdict_static_only":"static scan only (not pumped): no ambiguity construct found, and the no-ambiguous-choice-point argument holds for anchored application"}],"match_matrix":{"rows":[{"index":0,"label":"positive","string":"AB-1234","verdict":"pass","expected":"accept","observed":"accept","match_span":[0,7],"matched_text":"AB-1234"},{"index":1,"label":"positive","string":"XY-9999","verdict":"pass","expected":"accept","observed":"accept","match_span":[0,7],"matched_text":"XY-9999"},{"…":"7 further rows, one per example, never sampled"}],"summary":{"rows":9,"failures":0,"negatives_total":5,"positives_total":4,"negatives_rejected":5,"positives_accepted":4,"all_examples_satisfied":true},"complete":true,"match_mode":"fullmatch"},"_this_example":"Generated by calling this service with the 'input' example above, then abridged ONLY by the elisions marked '…'. Engine 1.0.0. POST the input to /v1/preview and diff it yourself.","status_meaning":"a pattern was found that accepts every positive and rejects every negative; the match matrix below is the complete evidence","near_miss_probes":{"what_this_is":"Strings NOT in your examples, generated by mutating them, with the chosen pattern's verdict on each. Every acceptance below is a generalisation we made on your behalf; every rejection is a boundary we drew. You are the only one who can say whether they match your intent.","accepted_count":24,"rejected_count":73,"accepted_sample":[{"string":"ZB-1234","mutation":"position 0 ('A') replaced with 'Z', same character class","derived_from":"AB-1234"}],"rejected_sample":[{"string":"ABB-1234","mutation":"run #0 one character longer","derived_from":"AB-1234"}]},"how_it_was_derived":{"strategy":"segment_profile","why_this_one":"every example has the same run structure (upper lit:- digit); each run became an observed class with bounded repetition; static backtracking scan: static scan only (not pumped): no ambiguity construct found, and the no-ambiguous-choice-point argument holds for anchored application; it satisfies every example, and among the 5 candidates that do, it ranked first under the published selection rule (it accepts 24 of the 97 near-miss probes, the most of any candidate at its structural rank)","candidates_generated":8,"candidates_satisfying_all_examples":5},"limits_of_this_answer":["… all 7 limits are in every response …"],"pattern_body_unanchored":"[A-Z]{2}-[0-9]{4}"}},"example":null,"exampleRequest":null,"tags":["x402"],"displayCostAmount":"0.1","displayCostAsset":"USDC","priceDynamic":false,"priceHint":null,"priceStatus":"priced","priceSource":"probe","requiresHandshake":false,"reviewCount":0,"rating":{"score":"0.00","successRate":"0.00","reviews":0,"stars":null,"state":"unrated"},"availabilityStatus":"down","priceObserved":null,"sessionDeposit":null,"pricing":{"kind":"static","summary":"$0.1/call","primary":{"kind":"static","protocol":"x402","network":"base","amountUsd":"0.1","per":"call","confidence":"exact"},"accepted":[{"kind":"static","protocol":"x402","network":"base","amountUsd":"0.1","per":"call","confidence":"exact"}]},"paymentMethods":[{"uid":"pm_1Rv9XB_soNDrsWPy7r081","protocol":"x402","methodType":"crypto","chain":"base","mode":"charge","costAmount":"0.1","costPer":"request","priority":0,"asset":"0x833589fCD6eDb6E08f4c7C32D4f71b54bdA02913","unit":"request","depositMicros":null,"planRef":null}],"brandName":null,"brandSlug":null,"brandBaseUrl":null,"brandDocsUrl":null,"whatItDoes":"Synthesizes a verified regular expression from labeled positive/negative examples and provides a full match matrix plus catastrophic-backtracking (ReDoS) safety analysis","exampleAgentPrompt":"Can you synthesize a regex that matches strings like 'AB-1234', 'ZZ-0099' and rejects strings like 'ab-1234', '1A-5678', 'AB-12'? I need the full match matrix showing every example and a ReDoS backtracking safety report.","exampleUseCases":[{"title":"Validate product SKU format","prompt":"I need a regex that matches product SKUs like 'TX-4501', 'NY-0023' and rejects anything that doesn't fit — like 'tx-4501', 'TX-45', or 'TX-45011'. Give me the complete match matrix and flag any ReDoS risk."},{"title":"Safe input sanitization for user IDs","prompt":"Build me a verified regex for user IDs that match patterns like 'usr_abc123', 'usr_xyz999' and reject 'usr_', 'abc123', 'usr_abc!@#'. I need to see every test case checked in the match matrix and a catastrophic-backtracking analysis before I ship it."},{"title":"Log parser pattern from sample lines","prompt":"Can you synthesize a regex from these server log lines I want to capture — '2024-01-15 ERROR 500', '2024-12-01 WARN 404' — and reject lines like 'ERROR 500', '2024-1-5 OK 200'? Show the full match matrix and tell me if there's any worst-case ReDoS input class."}],"resultDescription":"Returns a JSON object containing: (1) a synthesized regex pattern in a portable restricted subset guaranteed to accept all positives and reject all negatives, (2) a complete match matrix with one row per example showing expected vs observed result and the match span, (3) a ReDoS analysis with a structural verdict (e.g. 'linear_time_by_structural_argument'), named worst-case input class if found, a list of structural checks with pass/fail, and explicit notes when no worst-case was found, and (4) a cryptographically signed receipt (Ed25519) with SHA-256 hashes of the request and response for auditability.","failureModes":["No satisfying pattern exists for the given positive/negative sets — returns unsolved status","Contradictory examples (same string in both positives and negatives) cause rejection","Overly large or complex example sets may time out","Examples that require non-portable regex constructs outside the restricted subset cannot be synthesized","Malformed request body or missing required fields returns a validation error"],"whenToPreferThis":"Choose this endpoint when you need a regex that is guaranteed correct against a specific set of labeled examples rather than relying on a model to guess one that may fail silently in production. It is especially valuable when deploying regex to security-sensitive input validation where catastrophic backtracking (ReDoS) could be exploited, or when you need an auditable proof via signed receipt and a complete match matrix that you can independently verify. Prefer alternatives only if you need unrestricted PCRE constructs or lookaheads that fall outside the portable restricted subset this service produces.","instructions":null,"reviewSummary":null,"reviewSummaryHighlights":null,"reviewSummaryConcerns":null,"reviewSummaryGeneratedAt":null,"activationCount":0,"lastUsedAt":null,"lastSuccessfullyRanAt":null,"lastHealthCheckAt":"2026-09-15T21:27:42.631Z","isFirstParty":false}