비트 패턴 검색

🔍 Bit Pattern Search - Technical Reference Guide

개요

비트 패턴 검색은 CAN 버스의 원시 데이터(BLF 파일)에서 알려진 기준 신호(Reference Signal)와 유사한 패턴을 가진 비트 조합을 자동으로 찾아내는 기술입니다. DBC 파일 없이도 신호를 역추적(Reverse Engineering)할 수 있는 핵심 기술입니다.

---

1. 원시 CAN 데이터의 구조

1.1 BLF 파일의 실제 모습

CAN 버스에서 수집된 원시 데이터는 다음과 같은 형태로 저장됩니다:

시간(s)  채널  메시지ID   DLC  데이터 (Hex)
----------------------------------------------
0.000    0     0x123      8    01 23 45 67 89 AB CD EF
0.010    1     0x456      4    12 34 56 78
0.020    0     0x123      8    01 24 46 68 8A AC CE F0
0.030    2     0x789      6    AA BB CC DD EE FF
0.040    0     0x456      8    00 11 22 33 44 55 66 77
0.050    0     0x123      8    01 25 47 69 8B AD CF F1
...

특징:

• ✅ 여러 채널 공존: Ch0, Ch1, Ch2... (보통 CAN1, CAN2...)
• ✅ 다양한 메시지 ID: 0x123, 0x456, 0x789...
• ✅ 다른 DLC(길이): 4바이트, 6바이트, 8바이트...
• ✅ 메시지 혼재: 메시지들의 주기가 달라 뒤섞여 있음
• ✅ 16진수 표현: 실제 비트는 이진수로 처리됨

1.2 원시 데이터 시각화

Timeline: ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━>

Ch0 0x123: ●────────●────────●────────●────────●
Ch0 0x456: ─────────────●─────────────●─────────
Ch1 0x456: ──●───────────────●───────────────●──
Ch2 0x789: ────●────────────────●──────────────●
...

문제점: 이 혼돈 속에서 특정 신호를 어떻게 찾을까?

---

2. 1단계: 필터링 (Selection)

2.1 채널 및 메시지 ID 선택

검색할 대상을 좁히기 위해 특정 채널과 특정 메시지 ID를 선택합니다.

예시: Channel 0, Message ID 0x123만 추출

원시 데이터 (전체):
시간(s)  채널  메시지ID   DLC  데이터 (Hex)
----------------------------------------------
0.000    0     0x123      8    01 23 45 67 89 AB CD EF  ← 선택
0.010    1     0x456      4    12 34 56 78              ← 제외
0.020    0     0x123      8    01 24 46 68 8A AC CE F0  ← 선택
0.030    2     0x789      6    AA BB CC DD EE FF        ← 제외
0.040    0     0x456      8    00 11 22 33 44 55 66 77  ← 제외
0.050    0     0x123      8    01 25 47 69 8B AD CF F1  ← 선택

필터링 후 (Ch0, 0x123):
시간(s)  채널  메시지ID   DLC  데이터 (Hex)
----------------------------------------------
0.000    0     0x123      8    01 23 45 67 89 AB CD EF
0.020    0     0x123      8    01 24 46 68 8A AC CE F0
0.050    0     0x123      8    01 25 47 69 8B AD CF F1
...

결과: 분석 대상이 명확해지고 처리 속도가 향상됩니다.

---

3. 2단계: 비트 추출 (Bit Extraction)

3.1 메시지를 비트로 변환

선택된 메시지의 데이터를 비트 스트림으로 변환합니다.

예시: 01 23 45 67 89 AB CD EF (8바이트 = 64비트)

바이트:  D0   D1   D2   D3   D4   D5   D6   D7
헥스:    01   23   45   67   89   AB   CD   EF

비트 위치 (Little-Endian 기준):
   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ... 63
   │  │  │  │  │  │  │  │  │  │  │  │  │  │  │  │      │
   └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴── ...┘
   ◄──────D0─────► ◄──────D1─────► ◄──────D2─────►
      (01)             (23)             (45)

실제 비트:
[0][0][0][0][0][0][0][1][1][1][0][0][0][1][0][0]...

3.2 시작 비트 이동 (Sliding Window)

핵심 개념: 가능한 모든 시작 위치에서 신호를 추출해봅니다.

신호 크기: 16bit 가정

시작 비트 0:  [0][0][0][0][0][0][0][1][1][1][0][0][0][1][0][0]...
              ◄────────16bit 추출────────►

시작 비트 1:     [0][0][0][0][0][0][1][1][1][0][0][0][1][0][0][?]...
                 ◄────────16bit 추출────────►

시작 비트 2:        [0][0][0][0][0][1][1][1][0][0][0][1][0][0][?][?]...
                    ◄────────16bit 추출────────►

...

시작 비트 48: (64bit - 16bit = 최대 48까지 가능)

검색 범위: 시작 비트 0 ~ (DLC × 8 - 신호크기)

3.3 신호 크기 변경

서로 다른 신호 크기로 반복 검색합니다.

신호 크기 8bit:   ■■■■■■■■□□□□□□□□□□□□□□□□□□□□□□□□
신호 크기 12bit:  ■■■■■■■■■■■■□□□□□□□□□□□□□□□□□□□□
신호 크기 16bit:  ■■■■■■■■■■■■■■■■□□□□□□□□□□□□□□□□
신호 크기 24bit:  ■■■■■■■■■■■■■■■■■■■■■■■■□□□□□□□□

일반적인 검색 범위:

• 최소: 8bit (1바이트)
• 최대: 32bit (4바이트)
• 또는 사용자 지정 범위

---

4. 3단계: Endian 및 Sign 처리

4.1 Little-Endian vs Big-Endian

Little-Endian (Intel 방식):

바이트:    D0   D1   D2   D3
헥스:      01   23   45   67
비트 순서: LSB ←────────── MSB
           (낮은 주소에 낮은 바이트)

32bit: 0x 67 45 23 01
         └─┘└─┘└─┘└─┘
          D3 D2 D1 D0

Big-Endian (Motorola 방식):

바이트:    D0   D1   D2   D3
헥스:      01   23   45   67
비트 순서: MSB ──────────→ LSB
           (낮은 주소에 높은 바이트)

32bit: 0x 01 23 45 67
         └─┘└─┘└─┘└─┘
          D0 D1 D2 D3

검색 시: 두 가지 Endian으로 모두 시도합니다.

4.2 Unsigned vs Signed

Unsigned (부호 없음):

16bit 범위: 0 ~ 65535
예시: 0x8000 = 32768

Signed (2의 보수):

16bit 범위: -32768 ~ 32767
예시: 0x8000 = -32768 (MSB가 1이면 음수)

검색 시: 두 가지 타입으로 모두 시도합니다.

---

5. 4단계: 기준 신호와 비교

5.1 기준 신호(Reference Signal)

예시: 횡방향 가속도(Lateral Acceleration)

시간(s)   신호값(m/s²)
-----------------------
0.000     0.12
0.010     0.15
0.020     0.18
0.030     0.21
0.040     0.19
0.050     0.16
...

5.2 추출된 신호

각 (시작비트, 신호크기, Endian, Sign) 조합에서 추출한 Raw 값:

시간(s)   Raw값
--------------
0.000     123
0.020     145
0.050     167
...

5.3 상관계수(Correlation) 계산

핵심 원리: Factor와 Offset은 상관계수에 영향을 주지 않습니다!

# 상관계수는 "패턴의 유사도"만 측정
# Factor/Offset은 단순히 크기와 위치만 변경

Reference Signal:    [0.12, 0.15, 0.18, 0.21, 0.19, 0.16]
Extracted Raw:       [123,  145,  167,  189,  171,  149]

# Linear transformation: raw * factor + offset
# Factor = 0.001, Offset = 0.0
Transformed:         [0.123, 0.145, 0.167, 0.189, 0.171, 0.149]

# 상관계수 계산 (Pearson Correlation)
Correlation = 0.985  ← 매우 높은 상관관계!

수학적 배경:

Correlation(X, Y) = Correlation(aX + b, Y)
                  = Correlation(X, cY + d)

즉, 선형 변환은 상관계수를 바꾸지 않습니다.
따라서 Factor/Offset을 모르는 상태에서도 신호를 찾을 수 있습니다!

5.4 Factor와 Offset의 자동 계산

상관계수가 높은 후보를 찾은 후, 최적의 Factor/Offset을 계산합니다.

# 선형 회귀(Linear Regression)로 계산
# Physical = Raw × Factor + Offset

# 최적화 목표: RMSE 최소화
RMSE = sqrt(mean((Physical - (Raw × Factor + Offset))²))

# 결과:
Factor = 0.001234
Offset = -0.052

---

6. 전체 검색 프로세스

6.1 검색 공간

검색 대상 조합 = 채널 × 메시지 ID × 시작비트 × 신호크기 × Endian × Sign

예시 계산:
- 채널: 4개
- 메시지 ID (채널당): 평균 50개
- 시작비트 (메시지당): 평균 50개 (64bit - 신호크기)
- 신호크기: 10개 (8~32bit, 2bit 간격)
- Endian: 2개 (little, big)
- Sign: 2개 (unsigned, signed)

총 조합 = 4 × 50 × 50 × 10 × 2 × 2 = 400,000개!

6.2 검색 알고리즘

FOR each channel IN [0, 1, 2, 3]:
    FOR each msg_id IN message_ids:
        # 1단계: 메시지 필터링
        messages = filter_by_channel_and_id(blf_file, channel, msg_id)

        FOR each signal_size IN [8, 10, 12, 14, 16, 18, 20, 24, 32]:
            FOR each start_bit IN [0 to DLC*8 - signal_size]:
                FOR each endian IN ['little', 'big']:
                    FOR each sign IN ['unsigned', 'signed']:

                        # 2단계: 비트 추출
                        raw_signals = extract_bits(
                            messages, 
                            start_bit, 
                            signal_size, 
                            endian, 
                            sign
                        )

                        # 3단계: 시간 동기화
                        synced = time_sync(reference_signal, raw_signals)

                        # 4단계: 상관계수 계산
                        correlation = calculate_correlation(
                            reference_signal.values,
                            synced.raw_values
                        )

                        # 5단계: 필터링
                        IF correlation > threshold:
                            # 6단계: Factor/Offset 계산
                            factor, offset = optimize_linear_fit(
                                reference_signal.values,
                                synced.raw_values
                            )

                            # 7단계: RMSE 계산
                            rmse = calculate_rmse(
                                reference_signal.values,
                                synced.raw_values * factor + offset
                            )

                            # 8단계: 결과 저장
                            results.append({
                                'channel': channel,
                                'msg_id': msg_id,
                                'start_bit': start_bit,
                                'signal_size': signal_size,
                                'endian': endian,
                                'sign': sign,
                                'correlation': correlation,
                                'factor': factor,
                                'offset': offset,
                                'rmse': rmse
                            })

---

7. 실제 예시

7.1 Input

기준 신호: ESP_BrakePressure (DBC에서 추출)

시간(s)   압력(bar)
-------------------
0.00      0.0
0.01      0.5
0.02      1.2
0.03      2.1
0.04      2.8
0.05      3.2
...

BLF 파일: Taycan 주행 데이터 (20분, 5GB)

7.2 검색 설정

{
  "search_params": {
    "channels": [0, 1],
    "signal_sizes": [8, 12, 16, 20],
    "start_bit_step": 1,
    "endian_modes": ["little", "big"],
    "sign_modes": ["unsigned", "signed"],
    "min_correlation": 0.7,
    "max_lag_ms": 100
  }
}

7.3 검색 결과

상위 5개 후보:

1. Ch0 0x287 [Bit 24:35] 12bit Little Unsigned
   Correlation: 0.985
   Factor: 0.0122
   Offset: -0.15
   RMSE: 0.042

2. Ch0 0x287 [Bit 24:39] 16bit Little Signed
   Correlation: 0.981
   Factor: 0.00305
   Offset: 0.08
   RMSE: 0.051

3. Ch1 0x3A1 [Bit 8:19] 12bit Big Unsigned
   Correlation: 0.923
   Factor: 0.0125
   Offset: -0.20
   RMSE: 0.089

...

7.4 결과 해석

최적 후보 (1번):

• 메시지: Ch0, 0x287
• 비트 위치: 24~35 (12bit)
• 바이트 위치: D3의 하위 비트부터 시작
• Endian: Little
• Sign: Unsigned
• 물리값 계산: pressure = raw × 0.0122 - 0.15

검증:

# 비트 맵
Byte:  D0  D1  D2  D3  D4  D5  D6  D7
Bit:   0   8   16  24  32  40  48  56
                   ◄──12bit──►

# 추출 예시
메시지: 00 11 22 D3 D4 55 66 77
비트 24~35: [D3의 비트 0~7] + [D4의 비트 0~3]

---

8. 최적화 기법

8.1 병렬 처리

# 채널별 병렬 처리
with multiprocessing.Pool(processes=4) as pool:
    results = pool.map(search_channel, channels)

8.2 조기 종료 (Early Stopping)

# 상관계수가 낮으면 Factor/Offset 계산 생략
if correlation < min_correlation:
    continue  # 다음 조합으로

8.3 캐싱

# 메시지 추출 결과 캐싱
@lru_cache(maxsize=1000)
def get_messages(channel, msg_id):
    return extract_messages(blf_file, channel, msg_id)

---

9. 핵심 수식

9.1 비트 추출

Little-Endian, Unsigned:

def extract_bits_little_unsigned(data_bytes, start_bit, num_bits):
    # 전체 바이트를 하나의 정수로 변환
    value = int.from_bytes(data_bytes, byteorder='little', signed=False)

    # 비트 마스크 생성
    mask = (1 << num_bits) - 1

    # 시작 비트부터 추출
    extracted = (value >> start_bit) & mask

    return extracted

Big-Endian, Signed:

def extract_bits_big_signed(data_bytes, start_bit, num_bits):
    # 전체 바이트를 하나의 정수로 변환
    value = int.from_bytes(data_bytes, byteorder='big', signed=False)

    # 비트 마스크 생성
    mask = (1 << num_bits) - 1

    # 시작 비트부터 추출
    extracted = (value >> start_bit) & mask

    # 2의 보수로 signed 변환
    if extracted & (1 << (num_bits - 1)):
        extracted -= (1 << num_bits)

    return extracted

9.2 상관계수 (Pearson Correlation)

def pearson_correlation(x, y):
    """
    상관계수: -1 ~ 1
    1: 완벽한 양의 상관관계
    0: 무상관
    -1: 완벽한 음의 상관관계
    """
    n = len(x)

    # 평균
    mean_x = sum(x) / n
    mean_y = sum(y) / n

    # 편차
    dev_x = [xi - mean_x for xi in x]
    dev_y = [yi - mean_y for yi in y]

    # 공분산
    covariance = sum(dx * dy for dx, dy in zip(dev_x, dev_y))

    # 표준편차
    std_x = sqrt(sum(dx ** 2 for dx in dev_x))
    std_y = sqrt(sum(dy ** 2 for dy in dev_y))

    # 상관계수
    if std_x == 0 or std_y == 0:
        return 0

    correlation = covariance / (std_x * std_y)
    return correlation

9.3 선형 회귀 (Factor/Offset)

def linear_regression(x, y):
    """
    y = ax + b 의 a(factor), b(offset) 계산
    최소제곱법(Least Squares)
    """
    n = len(x)

    # 합계
    sum_x = sum(x)
    sum_y = sum(y)
    sum_xy = sum(xi * yi for xi, yi in zip(x, y))
    sum_x2 = sum(xi ** 2 for xi in x)

    # Factor (기울기)
    factor = (n * sum_xy - sum_x * sum_y) / (n * sum_x2 - sum_x ** 2)

    # Offset (절편)
    offset = (sum_y - factor * sum_x) / n

    return factor, offset

9.4 RMSE (Root Mean Square Error)

def calculate_rmse(y_true, y_pred):
    """
    실제값과 예측값의 차이를 측정
    작을수록 정확함
    """
    n = len(y_true)
    squared_errors = [(true - pred) ** 2 
                      for true, pred in zip(y_true, y_pred)]
    mse = sum(squared_errors) / n
    rmse = sqrt(mse)
    return rmse

---

10. 문제 해결 가이드

10.1 검색 결과가 없는 경우

원인 1: 임계값이 너무 높음

해결: min_correlation을 0.9 → 0.7로 낮춤

원인 2: 신호가 다른 메시지에 있음

해결: 검색할 채널/메시지 ID 범위 확대

원인 3: 신호 크기가 검색 범위 밖

해결: signal_sizes에 [6, 10, 14, 18, 22, 28] 등 추가

10.2 너무 많은 false positive

원인: 임계값이 너무 낮음

해결: 
- min_correlation을 0.7 → 0.85로 높임
- RMSE로 2차 필터링 (< 1.0)

10.3 검색 시간이 너무 오래 걸림

해결책:

1. 시간 범위 제한 (전체 대신 10~60초만)
2. 채널 수 줄이기 (관심 채널만)
3. start_bit_step을 1 → 2로 증가
4. 병렬 처리 활성화

---

11. 요약

핵심 원리

1. 필터링: 특정 채널/메시지 ID 선택
2. 슬라이딩 윈도우: 모든 비트 위치에서 시도
3. 조합 탐색: 크기/Endian/Sign의 모든 조합
4. 패턴 매칭: 상관계수로 유사도 측정
5. Factor/Offset 무관성: 선형 변환은 상관계수에 영향 없음
6. 자동 최적화: Factor/Offset은 나중에 계산

장점

• ✅ DBC 파일 없이도 신호 발견 가능
• ✅ 완전 자동화 (사람의 추측 불필요)
• ✅ 수학적으로 검증 가능
• ✅ 확장 가능 (다양한 신호 타입)

한계

• ⚠️ 계산량이 많음 (병렬 처리 필요)
• ⚠️ 기준 신호가 필요함
• ⚠️ 비선형 신호는 찾기 어려움
• ⚠️ 노이즈가 많으면 정확도 하락

---

12. 참고 자료

관련 도구

• 🎭 SignalCast: 기준 신호 생성
• 🎬 SignalDirector: 검색 설정 및 실행
• 🎞️ SignalTheater: 결과 시각화
• 🎨 SignalStudio: 후처리 및 정제

수학적 배경

• Pearson Correlation Coefficient
• Linear Regression (Least Squares)
• Root Mean Square Error (RMSE)
• Cross-correlation with lag

---

문서 버전: v1.0
작성일: 2026-01-03
대상 독자: CAN 신호 리버스 엔지니어링 실무자