R. Ryan Williams

67 papers A* 22A 10B 4Journal 29Unranked 1
YearRankTypeTitle / Venue / Authors
2025 J jnl
CoRR
R. Ryan Williams
2025 A* conf
STOC
R. Ryan Williams
2025 A* conf
STOC
Dean Doron, Edward Pyne, Roei Tell, R. Ryan Williams
2024 A conf
ITCS
Ce Jin, R. Ryan Williams, Nathaniel Young
2024 A* conf
STOC
Shuichi Hirahara, Rahul Ilango, R. Ryan Williams
2024 J jnl
CoRR
Marco Carmosino, Ronald Fagin, Neil Immerman, Phokion G. Kolaitis, Jonathan Lenchner, Rik Sengupta, R. Ryan Williams
2024 A* conf
STOC
R. Ryan Williams
2024 A conf
ITCS
Gabriel Bathie, R. Ryan Williams
2023 J jnl
CoRR
Shyan Akmal, Virginia Vassilevska Williams, R. Ryan Williams, Zixuan Xu
2023 J jnl
Algorithmica
Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, R. Ryan Williams
2023 A* conf
STOC
Rahul Ilango, Jiatu Li, R. Ryan Williams
2023 J jnl
Theory Comput. Syst.
Nikhil Vyas, R. Ryan Williams
2022 J jnl
CoRR
Lijie Chen, Ce Jin, Rahul Santhanam, R. Ryan Williams
2022 B conf
MFCS
Ronald Fagin, Jonathan Lenchner, Nikhil Vyas, R. Ryan Williams
2022 A conf
ITCS
Brynmor Chapman, R. Ryan Williams
2022 A* conf
SODA
Lijie Chen, Ce Jin, R. Ryan Williams, Hongxun Wu
2021 B conf
MFCS
Brynmor Chapman, R. Ryan Williams
2021 A conf
ITCS
Alexander Golovnev, Alexander S. Kulikov, R. Ryan Williams
2021 A* conf
LICS
R. Ryan Williams
2021 A* conf
FOCS
Lijie Chen, Ce Jin, Rahul Santhanam, R. Ryan Williams
2021 J jnl
ACM Trans. Algorithms
Timothy M. Chan, R. Ryan Williams
2021 J jnl
SIAM Rev.
R. Ryan Williams
2021 J jnl
CoRR
Shyan Akmal, R. Ryan Williams
2021 J jnl
J. Artif. Intell. Res.
Nikhil Vyas, R. Ryan Williams
2021 J jnl
CoRR
Brynmor Chapman, R. Ryan Williams
2021 A conf
ITCS
Abhijit Mudigonda, R. Ryan Williams
2021 J jnl
CoRR
Lijie Chen, Ce Jin, R. Ryan Williams, Hongxun Wu
2020 A* conf
FOCS
Lijie Chen, Xin Lyu, R. Ryan Williams
2020 J jnl
SIAM J. Comput.
Cody D. Murray, R. Ryan Williams
2020 A* conf
SODA
Josh Alman, Timothy M. Chan, R. Ryan Williams
2020 A conf
STACS
Nikhil Vyas, R. Ryan Williams
2020 J jnl
Electron. Colloquium Comput. Complex.
Lijie Chen, Ce Jin, R. Ryan Williams
2020 A* conf
STOC
Lijie Chen, Ce Jin, R. Ryan Williams
2020 J jnl
CoRR
Abhijit Mudigonda, R. Ryan Williams
2019 A* conf
FOCS
Lijie Chen, Ce Jin, R. Ryan Williams
2019 A conf
SAT
Nikhil Vyas, R. Ryan Williams
2019 A conf
CCC
Lijie Chen, Dylan M. McKay, Cody D. Murray, R. Ryan Williams
2019 J jnl
Electron. Colloquium Comput. Complex.
Lijie Chen, Dylan M. McKay, Cody Murray, R. Ryan Williams
2019 ch.
Computing and Software Science
R. Ryan Williams
2019 A conf
CCC
Lijie Chen, R. Ryan Williams
2019 A* conf
STOC
Dylan M. McKay, Cody D. Murray, R. Ryan Williams
2018 A* conf
STOC
Cody Murray, R. Ryan Williams
2018 conf
SOSA
R. Ryan Williams
2018 J jnl
SIAM J. Comput.
R. Ryan Williams
2018 J jnl
CoRR
R. Ryan Williams
2018 J jnl
Theory Comput.
R. Ryan Williams
2018 J jnl
J. ACM
Virginia Vassilevska Williams, R. Ryan Williams
2018 A* conf
SODA
Andrea Lincoln, Virginia Vassilevska Williams, R. Ryan Williams
2017 A* conf
SODA
Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, R. Ryan Williams, Huacheng Yu
2017 J jnl
Electron. Colloquium Comput. Complex.
Cody Murray, R. Ryan Williams
2017 A* conf
SODA
Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, R. Ryan Williams
2017 A* conf
FOCS
Amir Abboud, Aviad Rubinstein, R. Ryan Williams
2017 A conf
CCC
Cody D. Murray, R. Ryan Williams
2017 A* conf
SODA
Kasper Green Larsen, R. Ryan Williams
2017 B conf
IPEC
Andreas Björklund, Petteri Kaski, R. Ryan Williams
2017 J jnl
Theory Comput.
Cody D. Murray, R. Ryan Williams
2017 J jnl
CoRR
R. Ryan Williams
2017 A* conf
STOC
Josh Alman, R. Ryan Williams
2017 J jnl
ACM SIGLOG News
R. Ryan Williams
2017 J jnl
CoRR
Daniel M. Kane, R. Ryan Williams
2017 J jnl
CoRR
Andrea Lincoln, Virginia Vassilevska Williams, R. Ryan Williams
2016 A* conf
ICALP
Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, R. Ryan Williams
2016 J jnl
CoRR
Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, R. Ryan Williams
2016 J jnl
SIAM J. Comput.
R. Ryan Williams
2016 A* conf
FOCS
Josh Alman, Timothy M. Chan, R. Ryan Williams
2015 B conf
CSL
R. Ryan Williams
2008 J jnl
Comput. Complex.
R. Ryan Williams
redb/extractors/js_extractors/js_deobfuscation.py
← Index redb/extractors/js_extractors/js_deobfuscation.py python
import hashlib
import inspect
import re
from datetime import datetime, timezone
from typing import Any

from redb.extractors.enum import Tag
from redb.extractors.js_extractor import JSExtractor
from redb.extractors.js_extractors.js_patterns import PATTERNS

# String literals of 4+ characters; only used by the deobfuscation diff to count
# strings revealed after deobfuscation. Compiled once at module load.
_STRING_LITERAL_4PLUS_RE = re.compile(r"[\"\']([^\"\']{4,})[\"\']")


class JSDeobfuscationExtractor(JSExtractor):
    """Compute pre/post-deobfuscation metrics for a JS sample.

    The actual deobfuscation pass (external tool with jsbeautifier fallback)
    lives on `JSContext.deobfuscated` and is cached per sample, so any other
    extractor that needs the deobfuscated text reads the same value without
    re-running the subprocess. Configure the external tool via env vars:
        JS_DEOBFUSCATOR_PATH    Path or name (default: webcrack)
        JS_DEOBFUSCATE_TIMEOUT  Seconds (default: 60)
    """

    def __init__(
        self, filepath, log, exporters=None, index_prefix=None,
        known_benign=False, known_malicious=False, source=None, context=None,
    ):
        super().__init__(
            filepath, log, exporters, index_prefix,
            known_benign, known_malicious, source, context=context,
        )
        self.deobfuscation_result = None
        self.log.debug(inspect.currentframe().f_code.co_name)

    def tag(self):
        return Tag.JS_DEOBFUSCATION.value

    def extract(self):
        src = self.js_source
        if not src:
            return None

        deobfuscated, deobfuscator_used = self._context.deobfuscated
        if deobfuscated is None:
            return None

        original_size = len(src)
        original_entropy = self._context.text_entropy
        deobfuscated_size = len(deobfuscated)
        deobfuscated_entropy = self._calculate_text_entropy(deobfuscated)
        size_change_ratio = round(deobfuscated_size / original_size, 4) if original_size else 0.0

        # Strings revealed by deobfuscation: matched literals are extracted from
        # both versions and the set difference is the count of "new" strings.
        original_strings = set(_STRING_LITERAL_4PLUS_RE.findall(src))
        deobfuscated_strings = set(_STRING_LITERAL_4PLUS_RE.findall(deobfuscated))
        new_strings = deobfuscated_strings - original_strings

        # Suspicious APIs revealed by deobfuscation. Both sides of the diff
        # come from JSContext caches: the raw scan is computed once for the
        # whole pipeline; the deobfuscated scan is computed once and reused
        # by JSSuspiciousAPIsExtractor's revealed_by_deobf rows.
        original_apis = {n for n in self._context.scan if n in PATTERNS}
        deobfuscated_apis = set(self._context.scan_deobfuscated)
        new_apis = deobfuscated_apis - original_apis

        deobfuscated_sha256 = hashlib.sha256(deobfuscated.encode('utf-8')).hexdigest()

        self.deobfuscation_result = {
            'deobfuscator_used': deobfuscator_used,
            'deobfuscation_successful': True,
            'original_size': original_size,
            'deobfuscated_size': deobfuscated_size,
            'size_change_ratio': size_change_ratio,
            'original_entropy': original_entropy,
            'deobfuscated_entropy': deobfuscated_entropy,
            'new_strings_found': len(new_strings),
            'new_apis_found': len(new_apis),
            'deobfuscated_sha256': deobfuscated_sha256,
        }
        return self.deobfuscation_result

    def prepare_export_data(self, exporter_type: str) -> Any:
        if exporter_type == "ClickHouseExporter":
            if not self.deobfuscation_result:
                return None

            r = self.deobfuscation_result
            current_time = datetime.now(timezone.utc)
            data = [[
                self.sha256,
                r['deobfuscator_used'],
                int(r['deobfuscation_successful']),
                r['original_size'],
                r['deobfuscated_size'],
                r['size_change_ratio'],
                r['original_entropy'],
                r['deobfuscated_entropy'],
                r['new_strings_found'],
                r['new_apis_found'],
                r['deobfuscated_sha256'],
                current_time,
            ]]

            column_names = [
                "sha256", "deobfuscator_used", "deobfuscation_successful",
                "original_size", "deobfuscated_size", "size_change_ratio",
                "original_entropy", "deobfuscated_entropy",
                "new_strings_found", "new_apis_found",
                "deobfuscated_sha256", "analysis_date",
            ]

            column_type_names = [
                "FixedString(64)", "LowCardinality(String)", "UInt8",
                "UInt64", "UInt64", "Float64",
                "Float64", "Float64",
                "UInt32", "UInt32",
                "FixedString(64)", "DateTime64(3, 'UTC')",
            ]

            return (data, column_names, column_type_names)

    def get_clickhouse_table(self) -> str:
        return "redb_js_deobfuscation"