L* Algorithm(L star Algorithm) 이란? - 개념/예제/이해하기

L* Algorithm(L start Algorithm) 이란?

• 학생 - 선생
• 학생은 선생님에게 두가지 종류의 질문을 질문할 수 있음
  1. Membership Query : word w 가 언어 L 에 속하는지 아닌지 선생님은 yes or no를 답함
  2. Equivalence Query : DFA H가 L을 허용하는지 아닌지 여부. 허용하면 True 아니면 반례를 리턴함 x ∈ L\\L(H) ∪ L(H)\\L → L(H)는 무슨 뜻?
• 언어 L을 성공적으로 학습하려면 유한한 쿼리 내에서 DFA를 잘 guess 해야함.
• Language 라 하는 것은

예제: 로그인 프로토콜 추론

L* 알고리즘을 사용하여 네트워크 프로토콜을 추론하는 예제를 살펴보자.

아래는 학습자가 **네트워크 프로토콜의 상태와 동작(==Language)**을 추론하기 위해 L 알고리즘을 적용하는 방식을 나타낸다.

예를 들어, 간단한 로그인 프로토콜을 추론한다고 가정한다.

프로토콜 동작 가정

가상의 로그인 프로토콜이 다음과 같이 작동한다고 가정:

1. 사용자가 "LOGIN" 명령어를 보내면 서버는 "OK" 응답을 보냄
2. 사용자가 "AUTH" 명령어와 올바른 비밀번호를 함께 보내면, 서버는 "WELCOME" 응답을 보냄
3. 올바르지 않은 명령어를 보내면, 서버는 "ERROR"를 반환

이후 L* 알고리즘을 이용하여 이 로그인 프로토콜의 상태 머신을 추론

 

우리가 원하는 것 : 로그인 프로토콜의 상태머신 (DFA)를 추론

우리가 할 수 있는 것 : 선생님(서버)에게 질문(쿼리)를 날리고 그 결과 값을 받아올 수 있음.

 

1. 초기 설정

• 학습자: 프로토콜의 상태와 전이 규칙(==language)을 모르는 상태에서, 서버(선생님)에게 쿼리 보냄
• 선생님: 프로토콜 서버로, 학습자의 쿼리에 대해 올바른 응답("OK", "WELCOME", "ERROR")을 반환

2. 멤버십 쿼리와 초기 상태

학습자 → 선생님 쿼리를 보내고 그 응답을 확인함

쿼리 1: "LOGIN" — 서버 응답: "OK" (로그인 요청에 대해 승인)
쿼리 2: "AUTH password123" — 서버 응답: "ERROR" (로그인 없이 인증 요청)

초기 상태에서 학습자는 "LOGIN" 후에만 인증이 가능함을 추측.

따라서 LOGIN 명령이 로그인 상태로 진입하는 상태 전이를 나타낸다고 가정할 수 있습니다.

3. 상태 전이 추론 (추가 멤버십 쿼리)

학습자는 다음과 같은 멤버십 쿼리를 통해 상태 전이 조건을 추론합니다:

쿼리 3: "LOGIN", 그다음 "AUTH password123" — 서버 응답: "WELCOME" (로그인 이후 인증이 성공적으로 완료됨)
쿼리 4: "AUTH password123" — 서버 응답: "ERROR" (로그인 없이 인증 시도)

이 결과를 통해 학습자는 "LOGIN" 상태가 활성화된 후에만 인증 상태로 이동할 수 있다는 사실을 파악

이를 기반으로 다음과 같은 상태 전이를 구성가능:

초기 상태에서 "LOGIN" 명령어를 보내기만 함 → 인증 완료 여부와는 상관없이(이제 검사) 로그인 승인 상태로 이동
"로그인 승인 상태"에서 "AUTH password123" 명령어 → 인증 완료 상태로 이동

4. Equivalence Query와 반례로 상태 추가

이제 학습자는 Equivalence Query를 통해 가설로 만들어 놓은 state machine(DFA)이 올바른지 확인할 수 있다.

 

만약 학습자가 만든 DFA와 실제 프로토콜이 동등하지 않다면, 서버는 반례를 반환

지금까지 학습자가 만든 DFA가 다음과 같다고 가정

상태 1 (초기 상태): "LOGIN" → 상태 2
상태 2 (로그인 승인): "AUTH password123" → 상태 3 (인증 완료)

 

이 상태에서 Equivalence Query를 실행하여 다음과 같은 반례를 받는다(그냥 내가 직접 쏘고 되는지 안 되는지 확인)고 가정:

반례: "AUTH password123" — 서버 응답: "ERROR" (로그인 없이 인증 시도)

이 반례를 통해 학습자는 초기 상태에서 "AUTH" 명령어로는 인증을 받을 수 없다는 점을 명확히 하고, 인증 시도 이전에 반드시 "LOGIN"이 필요하다는 것을 알게됨.

 

따라서 ERROR 응답을 받을 수 있는 상태 전이를 상태 머신에 추가함.

 

그러니까.. AUTH password123 를 보냈을때 (동일한 메세지를 보냈을때) 어떤 경우에는 OK 어떤 경우에는 ERROR를 받는 다는 것을 알았기 때문에(state의 차이가 있다는 사실을 알았기 때문에) 새롭게 알게된 ERROR를 받는 경우에 대해 상태머신을 추가해줘야함.

 

즉, 로그인 상태가 아닌 상태에서 "AUTH" 명령을 받았을 때 "ERROR"로 이동하는 전이를 추가하여 상태 머신이 실제 프로토콜을 더 정확하게 반영해야함.

 

(참고 * : state라는게 중요한 이유는 동일한 단일 Message를 전달했을때 따른 결과 출력이 달라지는 경우를 표현하기 위함. 즉, 단일 메세지 관점에서 똑같은 메세지를 보냈는데 왜 얘는 Error 왜 얘는 Hello? 같은 사람에게 똑같은 말 한마디를 건넸는데 이사람이 기분이 나쁘면 -> 아 뭔소리야 이 사람이 기분이 좋으면 -> 그래^^ 하는 것과 같은 개념. 즉, 이 사람이 내가 건넨 말을 듣기 전에 뭐 어떤 말을 듣고 생각을 했길래(== 어떤 state가 형성되어있었길래) 그런 동작이 이루어졌는지를 파악하는게 궁극적인 목표)

 

5. 최종 추론된 DFA

학습자는 다음과 같은 DFA를 추론하게 됩니다:

상태 1 (초기 상태): "LOGIN" → 상태 2, 그 외의 입력은 "ERROR" 반환
상태 2 (로그인 승인): "AUTH password123" → 상태 3 (인증 완료), 그 외의 입력은 "ERROR" 반환
상태 3 (인증 완료): 모든 입력에 대해 "ERROR" 반환

 

이를 통해 학습자는 최종적으로 네트워크 로그인 프로토콜을 표현하는 DFA를 얻음.

결과적으로 아래와 같은 state-machine을 얻음

궁금정 정리

여기서 반례는 어떻게 answer? Teacher answers with a counterexample x ∈ L\\L(H) ∪ L(H)\\L

• 차집합 L\\L(H) :
  • 언어 L에는 속하지만 가설 DFA(H)는 모르는 아직 누락된 문자열 집합
  • 즉 아직 학습자의 DFA(H)가 파악하지 못한 영역
• 차집합 L(H)\\L :
  • 가설 DFA(H)에는 속하지만 언어 L에는 포함되지않는 잘못된 문자열 집합
  • 즉 학습자의 DFA(H)가 지금 잘 못 파악하고 있는 영역
• 합집합 L\\L(H) ∪ L(H)\\L :
  • 전체적으로 L과 L(H) : 학습자의 가설 DFA 사이의 차이점
  • 학습자가 만든 DFA(H)와 실제 목표 언어 L간의 모든 불일치를 나타냄(L에는 속하지만 DFA는 아직 모르는, DFA가 속한다고 잘 못 알고있는)
• 즉, 아래와 같이 DFA를 추론하고 있었을때

상태 2 (로그인 승인): "AUTH password123" → 상태 3 (인증 완료)

• 반례로 아래를 받는다면 (알게된다면)
  • 반례: "AUTH password123" — 서버 응답: "ERROR" (로그인 없이 인증 시도)
  • 추론하고 있었던 모델기준 L(H)\\L 에 해당하는 경우의 반례이다. 반례를 잘 만족시키도록 상태머신을 업데이트 해야한다.
  • 즉 아래와 같이 기존 DFA를 추론하고 있었을때

행복하세요 → 나가 죽어
(반례) 행복하세요 → 그래 너도 행복해

• • 위와 같이 응답을 받게 된다면 기존의 DFA를 아래와 같은 새로운 상태로 수정 해주어야한다. L(H)\\L

 

직접 구현 해보기

https://github.com/DES-Lab/AALpy

GitHub - DES-Lab/AALpy: An Automata Learning Library Written in Python

 

원문 : https://lateral-button-588.notion.site/L-start-Algorithm-12fbd773e511805f87e2d6ffc9e6b14c?pvs=4