{"service":"Pattern Synthesis + ReDoS Safety Report","operator":"Oddments","version":"1.0.0","summary":"Turn labelled examples into a verified regular expression. In: strings you want matched (positives) and strings you want rejected (negatives). Out: (1) a regex in a portable restricted subset, (2) THE COMPLETE MATCH MATRIX -- one row per example, every one, never sampled, each row showing expected vs observed with the match span, so you can re-check the whole claim yourself in one line, and (3) a CATASTROPHIC-BACKTRACKING (ReDoS) ANALYSIS naming a concrete worst-case input class WHEN THE METHOD FINDS ONE -- and saying explicitly when it did not, because this method can find backtracking and can never establish its absence. The pattern is not a suggestion: candidates that do not accept every positive and reject every negative are discarded before anything is returned, which 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, and 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 -- the same string labelled both ways, or a negative containing a positive under search semantics -- you get a PROOF of impossibility naming the conflict. TWO OUTCOMES TO KNOW ABOUT BEFORE YOU BUY. (a) If no structural generalisation survives your negatives, the guaranteed fallback is a pattern listing your positive examples VERBATIM (`^(?:AB-1234|XY-9999)$`) -- it matches those strings and nothing else, and it is labelled `literal_alternation` in the response. It is always ranked last, and more negatives are what push the synthesiser off it. (b) Rarely, no candidate separates your examples at all; status is `no_separating_pattern_found`, which -- unlike the two impossibility proofs -- is a limitation of this synthesiser and NOT a proof that no pattern exists. Both return HTTP 200 and both are billable, and we would rather you read that here than infer it from an invoice. Also returned: the ranked runners-up that also satisfy every example (static backtracking scan only, not pumped -- labelled as such), the derivation and the published selection rule, and 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, and a standalone verifier is served at /verify_receipt.py that 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, and 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 per call, published in every response. The emitted grammar is a restricted subset (literals, character classes, non-capturing groups, alternation, greedy quantifiers) with NO lookaround, backreferences, dot, negated classes or inline flags -- if you need those, this service structurally 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 that the returned pattern accepts every string you labelled positive and rejects every string you labelled negative. The match matrix is the complete evidence for exactly 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, and no amount of search fixes that. Rather than leave this as a disclaimer, every response includes a near-miss probe report: strings just outside your examples, with the pattern's verdict on each, so you can inspect the generalisation we made on your behalf. Likewise for the ReDoS analysis -- it is a bounded method (an enumerated static scan plus bounded empirical pumping) and it can find catastrophic backtracking but 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 describes the GENRE of document you get, a backtracking safety report, and is not a verdict about your pattern.","what_is_proved_and_what_is_not":{"headline":"WHAT IS PROVED AND WHAT IS NOT -- read this before buying. We prove that the returned pattern accepts every string you labelled positive and rejects every string you labelled negative. The match matrix is the complete evidence for exactly 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, and no amount of search fixes that. Rather than leave this as a disclaimer, every response includes a near-miss probe report: strings just outside your examples, with the pattern's verdict on each, so you can inspect the generalisation we made on your behalf. Likewise for the ReDoS analysis -- it is a bounded method (an enumerated static scan plus bounded empirical pumping) and it can find catastrophic backtracking but 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 describes the GENRE of document you get, a backtracking safety report, and is not a verdict about your pattern.","per_response_limits":["WHAT IS PROVED: the returned pattern accepts every string you labelled positive and rejects every string you labelled negative. The match matrix is the complete evidence for exactly that claim, and you can re-check every row yourself in one line.","WHAT IS NOT PROVED: that the pattern matches your INTENT. We see your examples; we do not 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. This limitation is not reducible by better search and we do not claim to have reduced it -- the near-miss probe report exists so you can inspect the generalisation we made.","The pattern is one of several that satisfy your examples; 'alternatives' lists the runners-up. The selection rule is published, but preferring the more general candidate is a design choice, not a derivation from your data.","Verification is by CPython's `re` with re.fullmatch (or re.search in search mode). The emitted syntax is a restricted portable subset, but we do NOT execute it in other engines, so behaviour in PCRE, JavaScript, Java, Go or Rust is argued from the subset, not measured.","The ReDoS analysis has its own separate limits, listed in full under redos.method_limits. In short: it is a bounded method, it never establishes absence, and this service does not use the word 'safe'.","If status is 'capped', a resource cap fired during the candidate search. The match matrix is still complete over your examples, but no claim is made that the returned pattern is the one this service would have selected with more time.","This service does not accept or execute buyer-supplied regular expressions or code. It analyses only the patterns it generated itself."],"redos_method_limits":["The static scan checks an ENUMERATED list of ambiguity constructs. It is not a decision procedure for regular-expression ambiguity; a construct not on the list is not checked for.","The empirical stage pumps a BOUNDED family of attack templates to BOUNDED lengths within a wall-clock deadline. Absence of blow-up in those trials is evidence, not proof.","Timings are wall-clock measurements of CPython's `re` on a 1-vCPU virtual machine. They are noisy at microsecond scale; the growth exponent is the signal and short runs can leave it unmeasurable.","Backtracking behaviour is engine-specific. Findings are argued for backtracking engines generally and measured on CPython `re` specifically. Another engine's optimiser may do better or worse on the same pattern.","This analyses the pattern ONLY. Denial of service through input size, request volume or the surrounding application is out of scope.","'no_catastrophic_backtracking_found' means this method found none. It does not mean the pattern is safe, and this service will not call a pattern safe.","Every claim here is conditioned on HOW the pattern is applied. Anchored vs `search`, and case-sensitive vs case-insensitive, change which findings hold; the 'applied_as' block records the assumptions this report was computed under. Apply the pattern differently and this report does not describe what you ran.","Only the CHOSEN pattern is pumped. The entries under 'alternatives' carry a static-scan result only, clearly labelled, with no empirical measurement."]},"endpoints":{"paid":{"method":"POST","path":"/v1/synthesize","price":"$0.10","protocol":"x402","network":"eip155:8453","asset":"USDC","pay_to":"0xf29Cc4af14aB4E4e17C320a8C8fB9AC4D476d935","caps":{"name":"paid","max_positives":200,"max_negatives":200,"max_examples_total":300,"max_example_length":512,"max_request_bytes":262144,"wall_seconds":4.0,"cpu_seconds":3.0,"memory_mb":512,"max_candidates":400,"max_alternatives_reported":8,"max_probes":400,"pump_max_length":4000,"pump_trials":6,"_note":"Requests over any of these limits are refused with a 400 before any search happens. wall/cpu/memory are enforced by the kernel in a forked child, not by cooperative checks."}},"free_preview":{"method":"POST","path":"/v1/preview","price":"free","caps":{"name":"free_preview","max_positives":6,"max_negatives":6,"max_examples_total":10,"max_example_length":64,"max_request_bytes":16384,"wall_seconds":2.0,"cpu_seconds":1.5,"memory_mb":256,"max_candidates":200,"max_alternatives_reported":3,"max_probes":80,"pump_max_length":2000,"pump_trials":4,"_note":"Requests over any of these limits are refused with a 400 before any search happens. wall/cpu/memory are enforced by the kernel in a forked child, not by cooperative checks."}},"errors":"/v1/errors","metrics":"/v1/metrics","openapi":"/openapi.json","receipt_public_key":"/.well-known/oddments-receipts.json","receipt_verifier":"/verify_receipt.py"},"selection_rule":"Among the candidates that satisfy every example, ranked by: (1) fewest backtracking risks found by the static scan -- a pattern that is a denial of service is not a better answer for being tidier; (2) how much structure it preserves, most-structural first (per-run generalisation, then alternation of run structures, then common affix, then a single whole-string class, and literal memorisation of your examples strictly last); (3) within the same strategy, the MORE general of two candidates, because the failure mode this product exists to prevent is a pattern that memorises the examples and breaks in production; (4) shorter pattern text; (5) lexicographic, so the choice is deterministic and the receipt reproducible.","example_request":{"positives":["AB-1234","XY-9999","QQ-0001","ZZ-4242"],"negatives":["ab-1234","AB-123","AB1234","AB-12345","A-1234"],"options":{"match_mode":"fullmatch"}},"input_schema":{"type":"object","title":"SynthesizeRequest","properties":{"positives":{"type":"array","minItems":1,"maxItems":200,"items":{"type":"string","maxLength":512},"description":"strings the pattern MUST accept. Required."},"negatives":{"type":"array","maxItems":200,"items":{"type":"string","maxLength":512},"description":"strings the pattern MUST reject. Optional, but they are what stops the synthesiser generalising further than you meant -- the more of these, the tighter the answer."},"options":{"type":"object","properties":{"match_mode":{"type":"string","enum":["fullmatch","search"],"default":"fullmatch","description":"fullmatch anchors the pattern to the whole string; search accepts a match anywhere in it"},"case_insensitive":{"type":"boolean","default":false,"description":"apply the case-insensitive flag when matching"},"include_probes":{"type":"boolean","default":true,"description":"return the near-miss generalisation report. On by default because it is the answer to this product's main limitation."}}}},"required":["positives"]},"output_schema":{"type":"object","title":"SynthesizeResponse","properties":{"status":{"type":"string","enum":["solved","capped","contradictory_examples","impossible_under_search_semantics","no_separating_pattern_found"]},"status_meaning":{"type":"string"},"pattern":{"type":["string","null"],"description":"the anchored regex"},"pattern_body_unanchored":{"type":["string","null"]},"match_matrix":{"type":"object","description":"the certificate: one row per example, complete, never sampled","properties":{"complete":{"type":"boolean"},"match_mode":{"type":"string"},"summary":{"type":"object","properties":{"positives_total":{"type":"integer"},"positives_accepted":{"type":"integer"},"negatives_total":{"type":"integer"},"negatives_rejected":{"type":"integer"},"rows":{"type":"integer"},"failures":{"type":"integer"},"all_examples_satisfied":{"type":"boolean"}}},"rows":{"type":"array","items":{"type":"object","properties":{"label":{"type":"string","enum":["positive","negative"]},"string":{"type":"string"},"expected":{"type":"string","enum":["accept","reject"]},"observed":{"type":"string","enum":["accept","reject"]},"verdict":{"type":"string","enum":["pass","FAIL"]},"match_span":{"type":"array","items":{"type":"integer"}}}}}}},"redos":{"type":"object","description":"catastrophic-backtracking analysis of the emitted pattern","properties":{"verdict":{"type":"string","enum":["no_backtracking_by_construction","no_catastrophic_backtracking_found","polynomial_backtracking_found","exponential_backtracking_found","not_analysed"]},"verdict_meaning":{"type":"string"},"structural_checks":{"type":"array","items":{"type":"object"}},"empirical_pumping":{"type":"object"},"worst_case_input_class":{"type":["object","null"],"description":"the input family that triggers the worst case, if one was found"},"method":{"type":"string"},"method_limits":{"type":"array","items":{"type":"string"}}}},"near_miss_probes":{"type":["object","null"],"description":"strings just outside your examples, and what the pattern does with them"},"alternatives":{"type":"array","description":"runners-up that also satisfy every example","items":{"type":"object"}},"impossibility_proof":{"type":["object","null"],"description":"present when your examples admit no pattern at all"},"dialect":{"type":"object"},"limits_of_this_answer":{"type":"array","items":{"type":"string"}},"receipt":{"type":"object"},"engine":{"type":"object"},"how_it_was_derived":{"type":"object","description":"the derivation itself: strategy, why it was chosen, how many candidates were generated, examined and satisfied every example, and the selection rule that picked the winner"},"alternatives_note":{"type":"string","description":"what the entries in `alternatives` do and do not have in common with the chosen pattern -- they all satisfy every example and differ only in how much they generalise"},"request_echo":{"type":"object","description":"what we understood you to have asked: example counts, distinct counts, match mode and case sensitivity. Echoed so a mis-parse is visible without re-reading your own request"},"caps_applied":{"type":"object","description":"the named cap set this request actually ran under (`paid` or `free_preview`) with every limit spelled out, so a `capped` status is attributable to a specific number"},"elapsed_ms":{"type":"integer","description":"wall time spent synthesising, excluding transport"},"preview":{"type":"object","description":"present on the FREE endpoint only (/v1/preview). Names the preview caps and the paid caps they correspond to, so the sample is legible as a sample. Absent from a paid response."}},"required":["status","limits_of_this_answer","receipt","engine"]},"metadata_floor":{"note":"The eight-item legibility floor this service was built to. Published because a buyer agent evaluating a catalog can check it mechanically.","items":{"1_description":"present -- see 'description' here and in /openapi.json","2_service_name":"Pattern Synthesis + ReDoS Safety Report","3_tags":["regex","pattern-synthesis","redos","security","catastrophic-backtracking","program-synthesis","verifiable","match-matrix","signed-receipt","validation","examples-to-regex","static-analysis"],"4_input_schema":"https://s3.oddments.ai/openapi.json and 'input_schema' below","5_output_schema":"https://s3.oddments.ai/openapi.json and 'output_schema' below","6_free_sample_verifying_the_paid_claim":"POST /v1/preview -- same shape, same complete matrix, same ReDoS report, same signed receipt","7_error_taxonomy":"https://s3.oddments.ai/v1/errors","8_listing_freshness":"every price or metadata change is pushed to every directory carrying us and the listing re-read against this endpoint before the change is considered done (PROD-11). S3 has two published x402scan listings -- the s3.oddments.ai origin and the legacy oddments-s3.exe.xyz origin -- and both are refreshed on every change. Each origin describes itself with its own hostname, so neither listing claims to be the other."}},"scope_boundary":"This service synthesises patterns from examples and analyses the patterns it generated. It does NOT accept a buyer-supplied regular expression to analyse, and it does not execute buyer-supplied code of any kind.","engine":{"service":"oddments-s3","version":"1.0.0","python":"3.12.3","regex_engine":"CPython stdlib `re` 2.2.1","synthesis_algorithm":"segment-profile generalisation + filtered candidate ranking, v1","redos_method":"static ambiguity scan (re-parsed from the emitted pattern) + bounded empirical pumping, v1","verification":"re.fullmatch (strictest anchoring; see dialect_notes)"},"public_base":"https://s3.oddments.ai","also_served_at":["https://oddments-s3.exe.xyz"]}