Principle:Liu00222 Open Prompt Injection Binary Search Localization
| Knowledge Sources | |
|---|---|
| Domains | Prompt_Injection, Security, Algorithm |
| Last Updated | 2026-02-14 15:00 GMT |
Overview
An efficient algorithm that uses binary search combined with an injection detector to identify the precise segment indices where injected content begins and ends within a segmented text.
Description
Binary Search Localization reduces the number of detector queries needed to find injection boundaries from O(n) to O(log n) per boundary. Starting with the full segment range, it progressively halves the search space: if concatenating segments in the left half triggers the detector, the injection start is in the left half; otherwise, it is in the right half. After finding the injection start, it uses causal influence analysis (via a GPT-2 helper model) to determine where the injected data ends and clean data resumes. This approach handles multiple injection regions by iterating the search after each found region.
Usage
Use this principle as the core localization algorithm within the PromptLocate pipeline. It is called after text segmentation and before interval merging and data recovery.
Theoretical Basis
Pseudo-code Logic:
# Binary search for injection start
def binary_search(segments, start, end, detector, prefix):
if start >= end:
return start
mid = (start + end) // 2
test_text = prefix + join(segments[start:mid+1])
if detector.query(test_text) == 1: # Contaminated
return binary_search(segments, start, mid, detector, prefix)
else:
return binary_search(segments, mid+1, end, detector, prefix)
# Full localization with multiple regions
injection_regions = []
while remaining_contaminated_range:
start = binary_search(segments, ...)
end = find_data_end(segments, start, causal_influence_model)
injection_regions.append([start, end])
The algorithm achieves O(log n) queries per injection boundary, with memoization caching to avoid redundant detector calls.