Tối ưu hóa quy tắc Sigma trong Spark bằng thuật toán Aho-Corasick | của Jean-Claude Côte | Tháng 6 năm 2024

Mở rộng Spark để cải thiện hiệu suất trong việc xử lý nhiều cụm từ tìm kiếm

Trong quá trình triển khai hệ thống phát hiện xâm nhập vào sản xuất tại CCCS, chúng tôi nhận thấy rằng nhiều quy tắc SigmaHQ sử dụng danh sách mẫu tìm kiếm rất lớn. Những danh sách này được sử dụng để kiểm tra xem một CommandLinechứa một chuỗi nhất định hoặc nếu CommandLinebắt đầu bằng hoặc kết thúc bằng một chuỗi con nhất định.

Chúng tôi đặc biệt quan tâm đến việc điều tra các quy tắc liên quan đến điều kiện “chứa”, vì chúng tôi nghi ngờ rằng Spark có thể tốn nhiều thời gian để đánh giá những điều kiện này. Đây là một ví dụ về quy tắc Sigma điển hình:

detection:
selection_image:
- Picture|accommodates:
- 'CVE-202'
- 'CVE202'
- Picture|endswith:
- 'poc.exe'
- 'artifact.exe'
- 'artifact64.exe'
- 'artifact_protected.exe'
- 'artifact32.exe'
- 'artifact32big.exe'
- 'obfuscated.exe'
- 'obfusc.exe'
- 'meterpreter'
selection_commandline:
CommandLine|accommodates:
- 'inject.ps1'
- 'Invoke-CVE'
- 'pupy.ps1'
- 'payload.ps1'
- 'beacon.ps1'
- 'PowerView.ps1'
- 'bypass.ps1'
- 'obfuscated.ps1'

Bạn có thể tìm thấy quy tắc Tên chương trình đáng ngờ đầy đủ tại đây
https://github.com/SigmaHQ/sigma/blob/master/rules/windows/process_creation/proc_creation_win_susp_progname.yml

Quy tắc này minh họa việc sử dụng CommandLine|accommodates và của Picture|endswith. Một số quy tắc Sigma có hàng trăm cụm từ tìm kiếm theo một |accommodatestình trạng.

Áp dụng quy tắc Sigma với Spark SQL

Tại CCCS, chúng tôi dịch các quy tắc Sigma thành các câu lệnh Spark SQL có thể thực thi được. Để làm như vậy, chúng tôi đã mở rộng trình biên dịch SQL Sigma với phần phụ trợ tùy chỉnh. Nó dịch quy tắc trên thành một tuyên bố như thế này:

choose
map(
'Suspicious Program Names',
(
(
(
Imagepath LIKE '%cve-202%'
OR Imagepath LIKE '%cve202%'
)
OR (
Imagepath LIKE '%poc.exe'
OR Imagepath LIKE '%artifact.exe'
...
OR Imagepath LIKE '%obfusc.exe'
OR Imagepath LIKE '%meterpreter'
)
)
OR (
CommandLine LIKE '%inject.ps1%'
OR CommandLine LIKE '%invoke-cve%'
OR CommandLine LIKE '%pupy.ps1%'
...
OR CommandLine LIKE '%encode.ps1%'
OR CommandLine LIKE '%powercat.ps1%'
)
)
) as sigma_rules_map

Chúng tôi chạy câu lệnh trên trong công việc phát trực tuyến có Cấu trúc Spark. Chỉ trong một lần lướt qua các sự kiện, Spark đánh giá nhiều (hàng trăm) quy tắc Sigma. Các sigma_rules_map cột chứa kết quả đánh giá của tất cả các quy tắc này. Sử dụng bản đồ này, chúng ta có thể xác định quy tắc nào là thành công và quy tắc nào không.

Như chúng ta có thể thấy, các quy tắc thường liên quan đến việc so sánh thuộc tính của sự kiện, chẳng hạn như CommandLinethành nhiều mẫu chuỗi.

Một số thử nghiệm này là kết quả trùng khớp chính xác, chẳng hạn như CommandLine = ‘one thing’. Những người khác sử dụng startswithvà được hiển thị dưới dạng Imagepath LIKE ‘%poc.exe’.

Equals, startswithVà endswith được thực thi rất nhanh vì các điều kiện này đều được neo ở một vị trí cụ thể trong thuộc tính của sự kiện.

Tuy nhiên, những thử nghiệm như accommodates được hiển thị dưới dạng CommandLine LIKE ‘%hound.ps1%’ yêu cầu Spark quét toàn bộ thuộc tính để tìm vị trí bắt đầu có thể có cho chữ ‘h’ và sau đó kiểm tra xem nó có theo sau là chữ ‘o’, ‘u’, v.v.

Trong nội bộ, Spark sử dụng một UTF8String nó lấy ký tự đầu tiên, quét bộ đệm và nếu tìm thấy kết quả khớp, hãy tiếp tục so sánh các byte còn lại bằng cách sử dụng matchAt chức năng. Đây là việc thực hiện các UTF8String.accommodates chức năng.

  public boolean accommodates(ultimate UTF8String substring) {
if (substring.numBytes == 0) {
return true;
}
byte first = substring.getByte(0);
for (int i = 0; i <= numBytes - substring.numBytes; i++) {
if (getByte(i) == first && matchAt(substring, i)) {
return true;
}
}
return false;
}

Các equals, startswithVà endswith điều kiện cũng sử dụng matchAt chức năng nhưng trái ngược với accommodates những điều kiện này biết bắt đầu so sánh từ đâu và do đó thực hiện rất nhanh.

Để xác nhận giả định của chúng tôi rằng accommodates điều kiện thực hiện tốn kém, chúng tôi đã tiến hành một thí nghiệm nhanh chóng và đơn giản. Chúng tôi đã loại bỏ tất cả accommodates điều kiện cho các quy tắc Sigma để xem nó sẽ tác động như thế nào đến thời gian thực hiện tổng thể. Sự khác biệt rất đáng kể và khuyến khích chúng tôi theo đuổi ý tưởng triển khai chức năng Spark Catalyst tùy chỉnh để xử lý accommodates hoạt động liên quan đến số lượng lớn các thuật ngữ tìm kiếm.

Thuật toán Aho-Corasick

Một chút nghiên cứu đã đưa chúng tôi đến Thuật toán Aho-Corasick có vẻ phù hợp cho trường hợp sử dụng này. Thuật toán Aho-Corasick xây dựng một cây tiền tố (một trie) và có thể đánh giá nhiều accommodates các biểu thức trong một lần chuyển qua văn bản cần kiểm tra.

Đây là cách sử dụng triển khai Java Aho-Corasick từ Robert Bor có sẵn trên github tại đây https://github.com/robert-bor/aho-corasick

// create the trie
val triBuilder = Trie.builder()
triBuilder.addKeyword("test1")
triBuilder.addKeyword("test2")
trie = triBuilder.construct()
// apply the trie to some textual content
aTextColumn = "some textual content to scan for both test1 or test2"
discovered = trie.containsMatch(aTextColumn)

Thiết kế một aho_corasick_in Chức năng tia lửa

Hàm của chúng ta sẽ cần hai thứ: cột cần kiểm tra và các mẫu tìm kiếm cần tìm. Chúng tôi sẽ thực hiện một chức năng với chữ ký sau:

boolean aho_corasick_in(string textual content, array searches)

Chúng tôi đã sửa đổi trình biên dịch CCCS Sigma của mình để tạo ra các câu lệnh SQL sử dụng aho_corasick_inthay vì tạo ra nhiều vị từ ORed THÍCH. Trong kết quả đầu ra bên dưới, bạn sẽ nhận thấy việc sử dụng aho_corasick_in chức năng. Chúng tôi chuyển vào trường cần kiểm tra và một chuỗi các chuỗi để tìm kiếm. Đây là đầu ra của trình biên dịch tùy chỉnh của chúng tôi xử lý nhiều accommodates điều kiện:

choose 
map(
'Suspicious Program Names',
(
(
(
Imagepath LIKE '%cve-202%'
OR Imagepath LIKE '%cve202%'
)
OR (
Imagepath LIKE '%poc.exe'
OR Imagepath LIKE '%artifact.exe'
...
OR Imagepath LIKE '%meterpreter'
)
)
OR (
aho_corasick_in(
CommandLine,
ARRAY(
'inject.ps1',
'invoke-cve',
...
'hound.ps1',
'encode.ps1',
'powercat.ps1'
)
)
)
)
) as sigma_rules_map

Chú ý cách aho_corasick_in Hàm nhận hai đối số: đối số đầu tiên là một cột và đối số thứ hai là một mảng chuỗi. Bây giờ chúng ta hãy thực sự triển khai aho_corasick_inchức năng.

Thực hiện chức năng xúc tác

Chúng tôi không tìm thấy nhiều tài liệu về cách triển khai các hàm Catalyst nên thay vào đó, chúng tôi sử dụng mã nguồn của các hàm hiện có làm tài liệu tham khảo. Chúng tôi đã lấy regrec(str, regrec) hoạt động như một ví dụ vì nó biên dịch trước mẫu biểu thức chính quy và sau đó sử dụng nó khi xử lý các hàng. Điều này tương tự như việc xây dựng trước bộ ba Aho-Corasick và sau đó áp dụng nó cho mọi hàng.

Biểu thức xúc tác tùy chỉnh của chúng tôi có hai đối số. Vì thế nó là một BinaryExpression trong đó có hai trường mà Spark đặt tên left Và proper. Hàm tạo AhoCorasickIn của chúng tôi gán textual content đối số cột để left lĩnh vực và searches mảng chuỗi để proper cánh đồng.

Một việc khác chúng tôi làm trong quá trình khởi tạo AhoCorasickIn là đánh giá cacheTrie cánh đồng. Việc đánh giá kiểm tra xem liệu searches đối số là một biểu thức có thể gập lại, tức là một biểu thức không đổi. Nếu vậy, nó sẽ đánh giá nó và mong đợi nó là một mảng chuỗi mà nó sử dụng để gọi createTrie(searches).

Các createTrie hàm lặp lại các tìm kiếm và thêm chúng vào trieBuilder và cuối cùng xây dựng Aho-Corasick Trie.

case class AhoCorasickIn(textual content: Expression, searches: Expression) 
extends BinaryExpression 
with CodegenFallback 
with ImplicitCastInputTypes 
with NullIntolerant 
with Predicate {
override def prettyName: String = "aho_corasick_in"
// Assign textual content to left area 
override def left: Expression = textual content
// Assign searches to proper area 
override def proper: Expression = searches
override def inputTypes: Seq(DataType) = Seq(StringType, ArrayType(StringType))
// Cache foldable searches expression when AhoCorasickIn is constructed
non-public lazy val cacheTrie: Trie = proper match {
case p: Expression if p.foldable => {
val searches = p.eval().asInstanceOf(ArrayData)
createTrie(searches)
}
case _ => null
}
protected def createTrie(searches: ArrayData): Trie = {
val triBuilder = Trie.builder()
searches.foreach(StringType, (i, s) => triBuilder.addKeyword(s.toString()))
triBuilder.construct()
}
protected def getTrie(searches: ArrayData) = if (cacheTrie == null) createTrie(searches) else cacheTrie
override protected def nullSafeEval(textual content: Any, searches: Any): Any = {
val trie = getTrie(searches.asInstanceOf(ArrayData))
trie.containsMatch(textual content.asInstanceOf(UTF8String).toString())
}
override protected def withNewChildrenInternal(
newLeft: Expression, newRight: Expression): AhoCorasickIn =
copy(textual content = newLeft, searches = newRight)
}

Các nullSafeEval phương pháp này là trái tim của AhoCorasickIn. Spark gọi hàm eval cho mỗi hàng trong tập dữ liệu. TRONG nullSafeEvalchúng tôi truy xuất cacheTrie và sử dụng nó để kiểm tra textual content đối số chuỗi.

Đánh giá hiệu suất

Để so sánh hiệu suất của aho_corasick_in chúng tôi đã viết một tập lệnh đo điểm chuẩn nhỏ. Chúng tôi so sánh hiệu suất của việc thực hiện nhiều LIKE hoạt động so với một aho_corasick_in gọi.

choose
*
from (
choose
textual content like '%' || uuid() || '%' OR
textual content like '%' || uuid() || '%' OR
textual content like '%' || uuid() || '%' OR
...
as end result
from (
choose
uuid()||uuid()||uuid()... as textual content
from
vary(0, 1000000, 1, 32)
)
)
the place
end result = TRUE

Thí nghiệm tương tự sử dụng aho_corasick_in:

choose
*
from (
choose
aho_corasick_in(textual content, array(uuid(), uuid(),...) as end result
from (
choose
uuid()||uuid()||uuid()... as textual content
from
vary(0, 1000000, 1, 32)
)
)
the place
end result = TRUE

Chúng tôi đã chạy hai thử nghiệm này (như so với aho_corasick_in) với textual content cột 200 ký tự và số lượng từ tìm kiếm thay đổi. Đây là một biểu đồ logarit so sánh cả hai truy vấn.

Biểu đồ này cho thấy hiệu suất giảm sút như thế nào khi chúng tôi thêm nhiều cụm từ tìm kiếm hơn vào truy vấn “THÍCH”, trong khi truy vấn sử dụng aho_corasick_in chức năng vẫn tương đối ổn định khi số lượng thuật ngữ tìm kiếm tăng lên. Ở 100 cụm từ tìm kiếm, aho_corasick_in hàm chạy nhanh hơn năm lần so với nhiều câu lệnh THÍCH.

Chúng tôi nhận thấy rằng việc sử dụng Aho-Corasick chỉ mang lại lợi ích sau 20 lượt tìm kiếm. Điều này có thể được giải thích bằng chi phí ban đầu để xây dựng bộ ba. Tuy nhiên, khi số lượng cụm từ tìm kiếm tăng lên, chi phí trả trước đó sẽ được đền đáp. Điều này trái ngược với các biểu thức THÍCH, trong đó chúng ta càng thêm nhiều biểu thức THÍCH thì truy vấn càng trở nên tốn kém hơn.

Tiếp theo, chúng tôi đặt số lượng cụm từ tìm kiếm là 20 và thay đổi độ dài của textual content sợi dây. Chúng tôi quan sát thấy rằng cả THÍCH và aho_corasick_in mất khoảng thời gian như nhau trên các độ dài chuỗi khác nhau. Trong cả hai thử nghiệm, thời gian thực hiện phụ thuộc vào độ dài của textual content sợi dây.

Điều quan trọng cần lưu ý là chi phí phát sinh để xây dựng bộ ba sẽ phụ thuộc vào số lượng tác vụ Spark trong kế hoạch thực hiện truy vấn. Spark khởi tạo các biểu thức (tức là: khởi tạo các đối tượng AhoCorasickIn mới) cho mọi tác vụ trong kế hoạch thực hiện. Nói cách khác, nếu truy vấn của bạn sử dụng 200 tác vụ thì hàm tạo AhoCorasickIn sẽ được gọi 200 lần.

Tóm lại, chiến lược sử dụng sẽ phụ thuộc vào số lượng thuật ngữ. Chúng tôi đã tích hợp tính năng tối ưu hóa này vào trình biên dịch Sigma của mình. Dưới một ngưỡng nhất định (giả sử là 20 thuật ngữ), nó sẽ hiển thị các câu lệnh THÍCH và trên ngưỡng này, nó sẽ hiển thị một truy vấn sử dụng aho_corasick_in chức năng.

Tất nhiên, ngưỡng này sẽ phụ thuộc vào dữ liệu thực tế của bạn và số lượng nhiệm vụ trong kế hoạch thực hiện Spark của bạn.

Kết quả ban đầu của chúng tôi, được thực hiện trên dữ liệu sản xuất và các quy tắc SigmaHQ thực tế, cho thấy rằng việc áp dụng aho_corasick_in tăng tốc độ xử lý của chúng tôi (sự kiện mỗi giây) lên gấp 1,4 lần.

Phần kết luận

Trong bài viết này, chúng tôi đã trình bày cách triển khai hàm Spark gốc. Biểu thức Catalyst này tận dụng thuật toán Aho-Corasick, thuật toán có thể kiểm tra nhiều cụm từ tìm kiếm cùng một lúc. Tuy nhiên, như với bất kỳ cách tiếp cận nào, đều có sự đánh đổi. Việc sử dụng Aho-Corasick yêu cầu xây dựng một trie (cây tiền tố), điều này có thể làm giảm hiệu suất khi chỉ sử dụng một vài cụm từ tìm kiếm. Trình biên dịch của chúng tôi sử dụng một ngưỡng (số lượng cụm từ tìm kiếm) để chọn chiến lược tối ưu, đảm bảo thực hiện truy vấn hiệu quả nhất.