Date of Award

Fall 1-1-2025

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Computer Science

First Advisor

Piskac, Ruzica

Abstract

Modern computing systems face multifaceted challenges in security, privacy, and leakage resilience. This dissertation makes four key contributions to addressing these challenges through novel combinations of symbolic reasoning, machine learning, and neurosymbolic techniques. First, it develops symbolic AI techniques for analyzing side-channel vulnerabilities in low-level code and quantum computers. I introduce novel symbolic register analyses to automatically detect power side-channel vulnerabilities in constant-time cryptographic implementations. Additionally, I demonstrate an algebraic reconstruction method using Mixed-Integer Linear Programming (MILP) optimization to reverse-engineer quantum circuits from power traces, enabling extraction of proprietary circuit information. Second, my research pioneers automated learning of randomized self-reductions (RSRs). Informally, a randomized self-reduction allows computing a function's value at a specific point by evaluating it on random correlated points. While RSRs have applications in cryptography, complexity theory, and interactive proof systems, their discovery has remained a manual, expert-driven process for over four decades. I present BITWEEN, a method and tool for automated RSR learning that outperforms genetic algorithms, symbolic regression, and mixed-integer linear programming. I further introduce Agentic BITWEEN, a neurosymbolic approach where large language models dynamically discover novel query functions for RSR property discovery, moving beyond the fixed query patterns previously used in the literature. Third, the dissertation demonstrates practical applications of these learned randomized reductions in compiling effective countermeasures against power side-channel and fault injection attacks. It develops RSR-based protocols for securing classical cryptographic implementations and enabling private quantum multi-party computations on untrusted cloud providers. Finally, it explores advanced transformer-based neurosymbolic approaches to combinatorial reasoning problems. I present the first successful approach for training transformers to learn cubing heuristics for Cube-and-Conquer SAT solving through a neuro-symbolic post-training framework using Monte Carlo Tree Search, supervised fine-tuning, and direct preference optimization. The resulting models surpass frontier LLMs while matching the best symbolic heuristics. I also develop conflict-driven clause learning techniques enhanced by in-context learning for combinatorial search problems. Together, these contributions advance automated security analysis and resilience across classical and quantum domains by pioneering the integration of symbolic reasoning, optimization techniques, and machine learning for security applications.

Download

Share

COinS