regret

package module
v0.0.0-...-cacfa07 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Oct 16, 2025 License: MIT Imports: 7 Imported by: 0

README

regret - Regex Threat Detector

Don't regret your regex.

regret (Regex Threat) is a Go library that detects evil regex patterns before they bite you. It can be used for validating and analyzing regular expression patterns to prevent Regular Expression Denial of Service (ReDoS) attacks.

Quick Start

Library
import "github.com/theakshaypant/regret"

// Quick validation
safe := regret.IsSafe("(a+)+")  // false

// Detailed analysis with auto-generated adversarial inputs
score, _ := regret.AnalyzeComplexity("(a+)+")
// Score: 70/100, Complexity: O(2^n), HasEDA: true
// Pump patterns and worst-case inputs generated automatically
// Use score.WorstCaseInput for testing
CLI Tool
# Quick validation
regret check "(a+)+"

# Detailed analysis
regret analyze "(a+)+" --mode=thorough

# Test with adversarial input
regret test "(a+)+" --size=20

Installation

# Library
go get github.com/theakshaypant/regret

# CLI tool
go install github.com/theakshaypant/regret/cmd/regret@latest

Features

  • Fast Heuristics - Sub-microsecond pattern validation
  • Formal NFA Analysis - Detect EDA (exponential) and IDA (polynomial) ambiguity
  • Complexity Scoring - 0-100 scale with Big O notation
  • Adversarial Testing - Generate pump patterns that expose vulnerabilities
  • Multiple Validation Modes - Fast, Balanced, Thorough
  • CLI Tool - Complete command-line interface for CI/CD and developer workflows

The Problem

// This innocent-looking regex...
pattern := "(a+)+b"
input := "aaaaaaaaaaaaaaaaaaaaaaaac"

// ...can hang your application for seconds or minutes!

regret detects these dangerous patterns before they cause problems.

Common Evil Patterns

Pattern Issue Complexity
(a+)+ Nested quantifiers O(2^n) - Exponential
a*a* Overlapping quantifiers O(n²) - Quadratic
(a|ab)+ Overlapping alternation Polynomial
(.*)* Nested wildcards Exponential

Documentation

Complete documentation is available in the docs/ directory:

Getting Started
Reference
Understanding regret

Use Cases

  • ✅ Validate user input before using in regex
  • ✅ CI/CD integration to catch dangerous patterns
  • ✅ Security audits to find ReDoS vulnerabilities
  • ✅ Code review with automated pattern analysis
  • ✅ Performance testing with adversarial inputs
  • ✅ Pre-commit hooks to prevent unsafe patterns

Why regret?

  1. Multiple detection layers - Heuristics, NFA analysis, and adversarial testing
  2. Formal methods - Based on automata theory and academic research
  3. Both library & CLI - Use in code or as a standalone tool
  4. Production ready - Comprehensive testing and documentation
  5. CI/CD friendly - Exit codes, JSON output, configurable modes

Is regret right for you?

Not sure if you need regret? Check out the When to Use regret guide, which includes:

  • 🌳 Decision tree to evaluate if regret fits your needs
  • 👥 Personas (who should use regret?)
  • 📋 Scenarios (when to use regret?)
  • 💡 Integration examples for different roles
  • ❓ Common questions answered

TL;DR: Use regret if you accept regex from users, use Python/Ruby/JavaScript/PHP/Java, or want to prevent ReDoS attacks.

Important: Go RE2 Engine

regret validates Go-compatible regex patterns only. Go uses the RE2 engine, which intentionally excludes features that can cause catastrophic backtracking:

Not Supported (by design)
  • ❌ Lookaheads: (?=...) and (?!...)
  • ❌ Lookbehinds: (?<=...) and (?<!...)
  • ❌ Backreferences: \1, \2, etc.
  • ❌ Conditional expressions
What This Means for regret

Patterns with unsupported features are rejected:

regret.IsSafe("(?=.*[A-Z]).*")  // false - invalid syntax
regret.Validate("(?=.*[A-Z]).*") // error: "unsupported Perl syntax"

Why?

  • regret uses Go's regexp/syntax parser
  • Cannot analyze patterns that Go's parser rejects
  • This is correct - these patterns won't work in Go anyway
Use the Right Tool
  • For Go patterns → Use regret ✓
  • For PCRE/JavaScript patterns → Use PCRE-specific tools like safe-regex or rxxr2

See How It Works for more details.

License

MIT License - see LICENSE file for details.

Acknowledgments

Built with inspiration from:

This project was built using Cursor and Claude.

Built with ❤️ to make regex safer for everyone.

Documentation

Overview

Package regret provides validation and analysis for regex patterns to prevent Regular Expression Denial of Service (ReDoS) attacks.

Overview

When your application accepts regex patterns from untrusted sources (user input, configuration files, APIs), you need to ensure these patterns won't cause catastrophic backtracking. regret analyzes patterns using formal automata theory to detect both exponential (EDA) and polynomial (IDA) backtracking vulnerabilities.

Quick Start 

import "github.com/theakshaypant/regret"

// Quick safety check
if !regret.IsSafe("(a+)+") {
    return errors.New("unsafe regex pattern")
}

// Detailed validation
issues, err := regret.Validate(pattern)
if err != nil {
    return err
}
for _, issue := range issues {
    fmt.Printf("%s: %s\n", issue.Type, issue.Message)
}

Validation Modes

regret offers three validation modes with different performance characteristics:

  • Fast: Quick heuristics only (~microseconds) Best for hot paths and real-time validation

  • Balanced: Heuristics + NFA analysis (~milliseconds) Recommended for most use cases

  • Thorough: Full analysis + adversarial testing (~tens of milliseconds) Best for configuration validation and security auditing

Issue Detection

The library detects multiple types of dangerous patterns:

  • Exponential Backtracking (EDA): Patterns with exponentially many matching paths Example: (a+)+, (a|a)* Complexity: O(2^n)

  • Polynomial Backtracking (IDA): Patterns with polynomial ambiguity Example: a*a* (quadratic), a*a*a* (cubic) Complexity: O(n^k)

  • Nested Quantifiers: Quantifiers inside quantified groups Example: (x*)*, (\w+)+

  • Overlapping Alternation: Alternations with overlapping branches Example: (a|ab)+, (foo|foobar)*

  • Context-Dependent Issues: Patterns that are safe/unsafe based on context Example: ((a|a)*|.*) is unsafe, but (a|a)*.* is safe

Configuration

Customize validation behavior with Options: 

opts := &regret.Options{
    Mode:               regret.Balanced,
    Timeout:            100 * time.Millisecond,
    MaxComplexityScore: 70,
    Checks:             regret.CheckDefault,
    StrictMode:         true,
}
issues, err := regret.ValidateWithOptions(pattern, opts)

Complexity Analysis

Get detailed complexity metrics: 

score, err := regret.AnalyzeComplexity(pattern)
if err != nil {
    return err
}

fmt.Printf("Complexity: %d/100\n", score.Overall)
fmt.Printf("Time Complexity: %s\n", score.TimeComplexity)

if score.HasEDA {
    fmt.Println("Exponential backtracking detected!")
}
if score.HasIDA {
    fmt.Printf("Polynomial degree: O(n^%d)\n", score.PolynomialDegree)
}

Adversarial Input Generation

Adversarial inputs are automatically generated during complexity analysis: 

score, err := regret.AnalyzeComplexity("(a+)+")
if err != nil {
    return err
}

// Use auto-generated worst-case input
if score.WorstCaseInput != "" {
    fmt.Printf("Worst-case input: %s\n", score.WorstCaseInput)
}

// Or create custom inputs using pump components
if len(score.PumpPattern) > 0 {
    pump := &regret.PumpPattern{
        Pumps:  score.PumpPattern,
        Suffix: "x",
    }
    for n := 10; n <= 100; n += 10 {
        input := pump.Generate(n)
        start := time.Now()
        re.MatchString(input)
        fmt.Printf("n=%d, time=%v\n", n, time.Since(start))
    }
}

Use Cases

User-Facing Applications: 

func handleUserRegex(pattern string) error {
    if !regret.IsSafe(pattern) {
        return errors.New("unsafe pattern")
    }
    re := regexp.MustCompile(pattern)
    // Use safely...
    return nil
}

Configuration Validation: 

for _, pattern := range config.Patterns {
    issues, _ := regret.Validate(pattern)
    for _, issue := range issues {
        if issue.Severity >= regret.High {
            return fmt.Errorf("unsafe pattern: %s", issue.Message)
        }
    }
}

API Endpoints: 

opts := &regret.Options{
    Mode:    regret.Fast,
    Timeout: 50 * time.Millisecond,
}
issues, _ := regret.ValidateWithOptions(userPattern, opts)
if len(issues) > 0 {
    http.Error(w, "Invalid pattern", http.StatusBadRequest)
    return
}

Theory Background

regret uses formal automata theory to analyze patterns:

1. Parse regex into Abstract Syntax Tree (AST) 2. Construct Non-deterministic Finite Automaton (NFA) 3. Analyze NFA for ambiguity:

  • EDA (Exponential Degree of Ambiguity)
  • IDA (Infinite Degree of Ambiguity)

4. Calculate polynomial degree for IDA patterns 5. Perform context-aware analysis 6. Generate adversarial inputs (pumping)

This approach is based on academic research:

  • "Analyzing Catastrophic Backtracking Behavior in Practical Regular Expression Matching"
  • "Analyzing Matching Time Behavior of Backtracking Regular Expression Matchers by Using Ambiguity of NFA"

Performance

Typical performance characteristics: 

Operation           Fast Mode    Balanced Mode    Thorough Mode
----------------------------------------------------------------
Validation          1-10μs       1-5ms            10-50ms
Complexity Analysis N/A          5-20ms           20-100ms
Pump Generation     N/A          <1ms             1-10ms

Thread Safety

All public functions are safe for concurrent use. Options and results are immutable after creation.

Error Handling

The library returns meaningful errors:

  • ErrInvalidPattern: Syntactically invalid regex
  • ErrPatternTooLong: Pattern exceeds MaxPatternLength
  • ErrTimeout: Analysis exceeded configured timeout
  • ErrUnsupportedFeature: Pattern uses unsupported features

Version Information 

fmt.Println(regret.FullVersion())

More Information

See README.md for comprehensive documentation and examples. GitHub: https://github.com/theakshaypant/regret

Package regret provides validation and analysis for regex patterns to prevent Regular Expression Denial of Service (ReDoS) attacks.

The library analyzes regex patterns for dangerous constructs using formal automata theory, detecting both exponential (EDA) and polynomial (IDA) backtracking vulnerabilities.

Index

Constants

View Source 
const (
	// Version is the current version of the library.
	Version = "0.1.0"

	// VersionMajor is the major version number.
	VersionMajor = 0

	// VersionMinor is the minor version number.
	VersionMinor = 1

	// VersionPatch is the patch version number.
	VersionPatch = 0

	// VersionPrerelease indicates this is a pre-release version.
	VersionPrerelease = "alpha"
)

Version information for the regret library.

Variables

View Source 
var (
	// ErrInvalidPattern indicates the pattern is syntactically invalid.
	ErrInvalidPattern = errors.New("invalid regex pattern")

	// ErrPatternTooLong indicates the pattern exceeds the maximum allowed length.
	ErrPatternTooLong = errors.New("pattern too long")

	// ErrTimeout indicates the analysis exceeded the configured timeout.
	ErrTimeout = errors.New("analysis timeout exceeded")

	// ErrUnsupportedFeature indicates the pattern uses unsupported regex features.
	ErrUnsupportedFeature = errors.New("unsupported regex feature")
)

Functions

func FullVersion 

func FullVersion() string

FullVersion returns the full version string including pre-release suffix.

func IsSafe 

func IsSafe(pattern string) bool

IsSafe performs a quick safety check on a regex pattern using strict default settings. Returns true if the pattern is safe to use, false otherwise.

This function uses Fast mode with CheckDefault flags and is optimized for performance. For detailed information about issues, use Validate() instead.

Example: 

if !regret.IsSafe("(a+)+") {
    return errors.New("unsafe regex pattern")
}

Types

type CheckFlags 

type CheckFlags uint32

CheckFlags is a bitmask of checks to perform during validation. 

const (
	// CheckNestedQuantifiers detects nested quantifiers like (a+)+, (x*)*.
	CheckNestedQuantifiers CheckFlags = 1 << iota

	// CheckOverlappingAlternation detects alternations with overlapping branches like (a|ab)+.
	CheckOverlappingAlternation

	// CheckCatastrophicBacktrack detects patterns that cause catastrophic backtracking.
	CheckCatastrophicBacktrack

	// CheckUnboundedRepetition detects unbounded repetition without anchors like .*password.*.
	CheckUnboundedRepetition

	// CheckExponentialPaths detects patterns with exponential matching paths.
	CheckExponentialPaths

	// CheckComplexityScore calculates and validates complexity scores.
	CheckComplexityScore

	// CheckMemoryUsage estimates memory usage for pattern matching.
	CheckMemoryUsage

	// CheckNFAAmbiguity performs NFA analysis to detect EDA and IDA.
	CheckNFAAmbiguity

	// CheckPolynomialDegree detects and calculates polynomial backtracking degree.
	CheckPolynomialDegree

	// CheckContextAwareness analyzes pattern context and ordering for safety.
	CheckContextAwareness

	// CheckAll enables all available checks.
	CheckAll CheckFlags = ^CheckFlags(0)

	// CheckDefault includes the most important checks for typical use cases.
	CheckDefault = CheckNestedQuantifiers |
		CheckOverlappingAlternation |
		CheckCatastrophicBacktrack |
		CheckNFAAmbiguity
)

type Complexity 

type Complexity int

Complexity represents time or space complexity classes. 

const (
	// Constant represents O(1) complexity.
	Constant Complexity = iota

	// Linear represents O(n) complexity.
	Linear

	// Quadratic represents O(n²) complexity.
	Quadratic

	// Cubic represents O(n³) complexity.
	Cubic

	// Polynomial represents O(n^k) complexity for k > 3.
	Polynomial

	// Exponential represents O(2^n) complexity.
	Exponential

	// Unknown represents unknown or indeterminate complexity.
	Unknown
)

func (Complexity) BigO 

func (c Complexity) BigO() string

BigO returns the mathematical Big-O notation.

func (Complexity) String 

func (c Complexity) String() string

String returns the string representation of the complexity.

type ComplexityScore 

type ComplexityScore struct {
	// Overall is the overall complexity score (0-100).
	// Lower is better. Scores above 70 indicate problematic patterns.
	Overall int

	// TimeComplexity is the estimated worst-case time complexity.
	TimeComplexity Complexity

	// SpaceComplexity is the estimated space complexity.
	SpaceComplexity Complexity

	// HasEDA indicates if Exponential Degree of Ambiguity was detected.
	// This means the pattern has exponentially many ways to match input.
	HasEDA bool

	// HasIDA indicates if Infinite Degree of Ambiguity was detected.
	// This means the pattern has polynomially many ways to match input.
	HasIDA bool

	// PolynomialDegree is the degree of polynomial backtracking.
	// 2 = quadratic, 3 = cubic, etc. Only set if HasIDA is true.
	PolynomialDegree int

	// Metrics contains detailed metrics about the pattern.
	Metrics Metrics

	// WorstCaseInput is an example input that triggers worst-case behavior.
	WorstCaseInput string

	// PumpPattern contains the pump components for generating adversarial inputs.
	PumpPattern []string

	// Explanation is a human-readable explanation of the complexity analysis.
	Explanation string

	// Safe indicates whether the pattern is considered safe based on the analysis.
	Safe bool
}

ComplexityScore contains detailed complexity analysis results.

func AnalyzeComplexity 

func AnalyzeComplexity(pattern string) (*ComplexityScore, error)

AnalyzeComplexity performs detailed complexity analysis on a regex pattern.

This function provides comprehensive information including:

  • Complexity score (0-100)
  • Time and space complexity estimates
  • EDA/IDA detection
  • Polynomial degree (if applicable)
  • Detailed metrics
  • Adversarial input examples

Uses Thorough mode for complete analysis.

Example: 

score, err := regret.AnalyzeComplexity("(a+)+")
if err != nil {
    return err
}
fmt.Printf("Complexity: %d/100\n", score.Overall)
if score.HasEDA {
    fmt.Printf("Exponential backtracking detected!\n")
    fmt.Printf("Worst-case input: %s\n", score.WorstCaseInput)
}

type Issue 

type Issue struct {
	// Type is the type of issue detected.
	Type IssueType

	// Severity indicates how serious the issue is.
	Severity Severity

	// Position indicates where in the pattern the issue occurs.
	Position Position

	// Pattern is the problematic sub-pattern.
	Pattern string

	// Message is a human-readable description of the issue.
	Message string

	// Example is an example adversarial input that exploits this issue.
	Example string

	// Suggestion provides guidance on how to fix the issue.
	Suggestion string

	// Complexity is the local complexity contribution (0-100).
	Complexity int

	// Details contains additional technical details about the issue.
	Details map[string]interface{}
}

Issue represents a detected problem in a regex pattern.

func Validate 

func Validate(pattern string) ([]Issue, error)

Validate analyzes a regex pattern and returns all detected issues. Uses default options (Balanced mode with CheckDefault flags).

Returns a slice of issues (which may be empty) and an error if the pattern cannot be analyzed (e.g., syntax errors, timeout).

Example: 

issues, err := regret.Validate("(a+)+")
if err != nil {
    return fmt.Errorf("validation failed: %w", err)
}
for _, issue := range issues {
    fmt.Printf("Issue: %s at position %d\n", issue.Message, issue.Position.Start)
}

func ValidateWithOptions 

func ValidateWithOptions(pattern string, opts *Options) ([]Issue, error)

ValidateWithOptions analyzes a regex pattern with custom configuration options.

The validation process runs in multiple layers depending on the Mode:

  • Fast: Quick heuristics only (~microseconds)
  • Balanced: Heuristics + NFA analysis (~milliseconds)
  • Thorough: Full analysis + adversarial testing (~tens of milliseconds)

Returns a slice of issues (which may be empty) and an error if the pattern cannot be analyzed.

Example: 

opts := &regret.Options{
    Mode: regret.Balanced,
    Timeout: 100 * time.Millisecond,
    MaxComplexityScore: 70,
}
issues, err := regret.ValidateWithOptions(pattern, opts)

type IssueType 

type IssueType int

IssueType represents the type of issue detected. 

const (
	// NestedQuantifiers indicates nested quantifiers like (a+)+.
	NestedQuantifiers IssueType = iota

	// OverlappingAlternation indicates alternations with overlapping branches.
	OverlappingAlternation

	// RepeatedCaptureGroup indicates repeated capturing groups.
	RepeatedCaptureGroup

	// ExponentialBacktracking indicates exponential backtracking (EDA).
	ExponentialBacktracking

	// PolynomialBacktracking indicates polynomial backtracking (IDA).
	PolynomialBacktracking

	// UnboundedRepetition indicates unbounded repetition without anchors.
	UnboundedRepetition

	// AmbiguousPattern indicates ambiguous matching behavior.
	AmbiguousPattern

	// ComplexityThresholdExceeded indicates complexity score is too high.
	ComplexityThresholdExceeded

	// ContextuallyDangerous indicates pattern is dangerous in current context.
	ContextuallyDangerous
)

func (IssueType) String 

func (i IssueType) String() string

String returns the string representation of the issue type.

type Metrics 

type Metrics struct {
	// NestingDepth is the maximum quantifier nesting depth.
	NestingDepth int

	// QuantifierCount is the total number of quantifiers in the pattern.
	QuantifierCount int

	// AlternationCount is the number of alternation operators (|).
	AlternationCount int
}

Metrics contains detailed metrics about a regex pattern.

type Options 

type Options struct {
	// Mode controls the depth of analysis.
	// Default: Balanced
	Mode ValidationMode

	// Timeout sets the maximum time for analysis.
	// Analysis will return partial results if timeout is exceeded.
	// Default: 100ms for Balanced, 1s for Thorough
	Timeout time.Duration

	// Checks specifies which checks to perform (bitmask).
	// Default: CheckDefault
	Checks CheckFlags

	// MaxComplexityScore is the maximum acceptable complexity score (0-100).
	// Patterns with higher scores will be flagged.
	// Default: 70
	MaxComplexityScore int

	// MaxPatternLength is the maximum allowed pattern length.
	// Very long patterns can slow down analysis.
	// Default: 1000, set to 0 for no limit
	MaxPatternLength int

	// MaxNestingDepth is the maximum allowed quantifier nesting depth.
	// Default: 3
	MaxNestingDepth int

	// MaxQuantifiers is the maximum number of quantifiers allowed.
	// Default: 20
	MaxQuantifiers int

	// StrictMode treats warnings as errors.
	// Default: false
	StrictMode bool

	// AllowUnsafe skips validation (passthrough mode).
	// Use with caution, primarily for testing.
	// Default: false
	AllowUnsafe bool
}

Options configures the validation and analysis behavior.

func DefaultOptions 

func DefaultOptions() *Options

DefaultOptions returns the recommended default configuration.

func FastOptions 

func FastOptions() *Options

FastOptions returns options optimized for speed.

func ThoroughOptions 

func ThoroughOptions() *Options

ThoroughOptions returns options for comprehensive analysis.

type Position 

type Position struct {
	// Start is the starting byte offset in the pattern.
	Start int

	// End is the ending byte offset in the pattern.
	End int

	// Line is the line number for multiline patterns (1-indexed).
	Line int

	// Column is the column number (1-indexed).
	Column int
}

Position represents a location in the regex pattern.

type PumpPattern 

type PumpPattern struct {
	// Prefix is the initial string before the pumped section.
	Prefix string

	// Pumps contains the repeating components.
	// Multiple pumps can be interleaved or concatenated.
	Pumps []string

	// Suffix is the final string after the pumped section.
	// Often a character that doesn't match, forcing backtracking.
	Suffix string

	// Interleave indicates whether pumps should be interleaved.
	// If true: pump[0], pump[1], pump[0], pump[1], ...
	// If false: pump[0] * n, pump[1] * m, ...
	Interleave bool

	// Description explains what this pump pattern tests.
	Description string
}

PumpPattern represents a pattern for generating adversarial inputs. It uses the "pumping" technique to create progressively longer inputs that expose exponential or polynomial backtracking.

func (*PumpPattern) Generate 

func (p *PumpPattern) Generate(size int) string

Generate creates an adversarial input of the specified size. The size parameter controls how many times the pump components are repeated.

func (*PumpPattern) GenerateSequence 

func (p *PumpPattern) GenerateSequence(start, end, step int) []string

GenerateSequence creates a sequence of adversarial inputs with increasing sizes.

type Severity 

type Severity int

Severity represents the severity level of an issue. 

const (
	// Critical issues will definitely cause ReDoS attacks.
	Critical Severity = iota

	// High severity issues are very likely to be exploited.
	High

	// Medium severity issues are potentially problematic.
	Medium

	// Low severity issues are minor concerns.
	Low

	// Info provides informational messages without immediate risk.
	Info
)

func (Severity) String 

func (s Severity) String() string

String returns the string representation of the severity.

type ValidationMode 

type ValidationMode int

ValidationMode controls the depth of analysis performed. 

const (
	// Fast mode uses only quick heuristics (~microseconds).
	// Best for hot paths and user input validation.
	Fast ValidationMode = iota

	// Balanced mode includes syntax analysis and NFA ambiguity detection (~milliseconds).
	// Recommended for most use cases.
	Balanced

	// Thorough mode includes all checks plus adversarial input generation (~tens of milliseconds).
	// Best for configuration validation and security auditing.
	Thorough
)

func (ValidationMode) String 

func (v ValidationMode) String() string

String returns the string representation of the validation mode.

Source Files

View all Source files

Directories

Path Synopsis
internal
analyzer
Package analyzer implements complexity analysis for regex patterns.
 Package analyzer implements complexity analysis for regex patterns.
cli/cmd
cli/output
detector
Package detector implements pattern detection logic for identifying dangerous regex patterns.
 Package detector implements pattern detection logic for identifying dangerous regex patterns.
parser
Package parser provides NFA construction and analysis utilities for regex patterns.
 Package parser provides NFA construction and analysis utilities for regex patterns.
pump
Package pump provides adversarial input generation for regex testing.
 Package pump provides adversarial input generation for regex testing.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.