스포카 코드 난독화 컨테스트 2016
작성한지 1년 이상 지난 게시물입니다. 최신의 정보와 맞지 않는 내용을 포함할 수도 있습니다.
스포카의 작년 코딩 대회 주제가 주어진 일을 가장 짧은 코드로 해내는 사람이 우승하는 ‘코드 골프’였다면 올해는 코드를 최대한 알아보기 어렵게 만드는 ‘난독화’이다. 난독화 대회 페이지에도 나와있긴 하지만, 제출할 코드의 조건은 다음과 같다.
계산기 프로그램을 작성하세요. 프로그램은 아래의 조건들을 만족하여야 합니다.
- 프로그램 파일 명은 calc.py 로 설정합니다.
- 커맨드 라인의 인자를 통해 입력을 전달하고 계산 결과가 출력되어야 합니다.
- 사칙연산이 지원되어야 합니다.
- 연산자 우선순위는 일반적인 사칙연산의 규칙을 따릅니다. 곱셈과 나눗셈이 우선으로 평가되어야 하며, 같은 우선 순위 내의 연산은 순서대로 평가되어야 합니다.
- 괄호로 연산의 우선순위를 지정할 수 있어야 합니다.
- 소수점 연산이 지원되어야 합니다. 나눗셈 결과가 떨어지지 않는 경우에는 결과가 실수로 출력되어야 합니다.
- 소수점 아래가 있는 경우에는 최소 3자리 이상 출력되어야 합니다.
- 잘못된 식이 입력되면 0이 아닌 값이 반환값으로 설정되고 프로그램이 종료되어야 합니다. 에러 메시지를 출력하는 것은 자유입니다.
채점 기준에 독특한 조항이 하나 보였다.
문제 자체는 제출을 위한 최소 조건이며, 얼마나 독창적인 방법으로 코드를 작성했는가가 주된 평가 기준입니다. 따라서 채점은 전적으로 평가자의 주관적인 판단에 근거합니다. 자세한 평가 기준은 수상작 발표 때 공개하도록 하겠습니다.
코드 골프는 ‘가장 짧은 코드’라는 매우 객관적 기준이 있었지만 이번 대회는 조금 다르다. 그래서 나는 ‘예술성’에 사활을 걸어보기로 하였다.
난독화 목표
어떤 일을 진행하든 목표를 정하고 진행하면 방향을 잃지 않고 가는데 큰 도움이 된다. 이번 일도 마찬가지로 몇가지 대략적인 목표를 정하고 진행하기로 했다.
eval및exec함수를 직접적으로 사용하지 않기- 모든 문자열 리터럴을 제거하기
- 코드에 최소한의 글로벌 함수만 노출시키기
- 코드에 최소한의 파이썬 키워드만 노출시키기
- Flake8 테스트 통과 (그 어떤 상황에서도 멋을 잃지 말자!)
Getting Started
파이썬 표준 라이브러리만 사용해서 사칙연산 파서를 직접 작성하는 것이 그렇게 어려운 일은 아니지만, 그렇다고 몇분만에 뚝딱 만들어낼 정도로 단순한 문제 또한 아니다. 어느정도 시간을 들여서 해법을 고민하고 실제로 코딩해보고 디버깅 하면서 만들어 나가야 하는 성격의 것이다. 정직한 @김영호님은 스택을 이용해서 사칙 연산 어휘 분석기(lexical analyzer)와 해석기(parser)를 직접 구현했지만, 나는 조금 양아치(?)같은 방식으로 해결하기로 했다.
import subprocess
import sys
def parse(expr):
stmt = 'print({})'.format(expr)
p = subprocess.Popen(['python3', '-c', stmt],
stdout=subprocess.PIPE,
stderr=subprocess.PIPE)
r, _ = p.communicate()
return r.decode('utf-8').strip()
if __name__ == '__main__':
x = parse(sys.argv[1])
try:
float(x)
except ValueError:
sys.exit(1)
else:
print(x)
그렇다. 입력받은 수식을 다른 파이썬 인터프리터에 넘겨서 결과값을 출력하도록 하는 프로그램이다. (…) 사실, eval 나 exec 함수를 이용하는것과 별 차이가 없긴 하지만, 그렇다고 대놓고 그렇게 하다간 작년처럼 부정행위로 간주될까봐 조금은 걱정되기도 했고, 수식 파서보다는 난독화에 조금 더 집중해보고 싶은 마음이 컸다. 어쨌든 “계산기 프로그램을 작성하세요” 라고 했지, “사칙연산 파서를 직접 만드세요” 라는 말은 없었으니까 나는 결백해!
동적 임포트(import)
파이썬의 최대 장점이자 단점 중 하나는 실행 시간(run-time)에 모든 것을 바꿀 수 있다는 것이다. 패키지 임포트도 예외가 아니다.
아래와 같은 임포트 명령어를
import subprocess
import sys
다음과 같이 __import__ 함수를 통해서 해결할 수 있다.
subprocess, sys = map(__import__, ['subprocess', 'sys'])
getattr 함수
최소한의 글로벌 함수만 노출시키기 위해서 선택한 방법이 getattr 함수를 이용하는 것이었다.
다음과 같은 코드를
r, _ = p.communicate()
이렇게 바꿀 수 있다.
r, _ = getattr(p, 'communicate')()
조금 더 복잡한 예제를 보여주자면,
p = subprocess.Popen(['python3', '-c', stmt],
stdout=subprocess.PIPE)
r, _ = p.communicate()
return r.decode('utf-8').strip()
위와 같은 코드는 다음과 같이 바꿀 수 있다.
popen = getattr(subprocess, 'Popen')
args = ['python3', '-c', getattr('print({})', 'format')(expr)]
r, _ = getattr(
popen(args, stdout=getattr(subprocess, 'PIPE')),
'communicate')()
x = getattr(getattr(result, 'decode')('utf-8'), 'strip')()
키워드 인자를 딕셔너리로 변환
여기서 키워드 인자인 stdout을 코드에 노출시키지 않으려려면 이 또한 문자열 리터럴로 바꾸어줄 필요가 있다.
popen(args, stdout=getattr(subprocess, 'PIPE'))
이 부분을 다음과 같이 바꿔준다.
kwargs = {'stdout': getattr(subprocess, 'PIPE')}
popen(args, **kwargs)
글로벌 빌트인
글로벌 함수인 float은 다음과 같이 호출할 수 있다.
globals()['__builtins__'].float(x)
위의 getattr 예제와 함께 응용하면,
getattr(globals()['__builtins__'], 'float')(x)
이렇게 하는 이유는 모든 함수 호출을 문자열 리터럴로 바꾸어서 최소한의 글로벌 함수만 노출시키고, 나중에 문자열 리터럴을 난독화 하기 위함이다.
문자열 리터럴 제거
문자열 리터럴을 제거하는 방법에는 여러가지가 있겠지만, 어떤 능력자가 눈이 뱅글뱅글 돌아가는 난독화 코드를 만들어 놓은게 있어서, 이걸 참고하기로 했다.
먼저, 다음과 같이 문자열을 정수로 인코딩 하는 함수를 만든다. 제출할 코드에는 포함시키지 않고, 별도의 파일에 넣었다.
def encode_str(s):
codes = [ord(c) for c in s]
return sum(codes[i] * 256 ** i for i in range(len(codes)))
그럼 float이나 __builtins__ 같은 문자열들은 다음과 같이 정수로 인코딩할 수 있다.
>>> encode_str('float')
499850898534
>>> encode_str('__builtins__')
29516468994777367089179156319
지금에서야 든 생각인데, __builtins__처럼 엄청나게 큰 정수 값으로 인코딩 되는 긴 문자열을 다음과 같이 잘게 쪼개서 인코딩 했다면 난독화 된 코드의 길이를 줄일 수 있지 않았을까 하는 생각도 든다.
>>> encode_str('__buil'), encode_str('tins__')
(119200196747103, 104863563147636)
조금 더 잘게 쪼갤 수도 있다.
>>> encode_str('__bu'), encode_str('ilti'), encode_str('ns__')
(1969381215, 1769237609, 1600090990)
하지만, 나는 너무 게을렀고 이렇게까지 하지는 않았다. 덕분에 최종 코드 길이가 조금(?) 길어지긴 했지만 큰 문제라고 생각하지는 않는다. 오히려 ‘난독화’라는 관점에서 보면 더 좋을 수도 있다.
이렇게 인코딩 된 문자열을 다시 원래대로 되돌리는 함수가 필요하다.
(lambda _, __, ___: _(_, __, ___))(
lambda _, __, ___:
chr(___ % __) + _(_, __, ___ // __) if ___ else
chr(32)[1:],
256,
encoded)
자세한 설명은 이 코드를 작성한 Kurtovic씨의 포스트를 참고하도록 하자.
한가지 설명을 덧붙이자면, 원본 코드에는 다음과 같은 부분이 있는데,
(lambda: _).func_code.co_lnotab,
파이썬 2.7에서는 다음과 같이 빈 문자열 ''을 내어주지만,
>>> (lambda: _).func_code.co_lnotab
''
파이썬 3.5에서는 다음과 같이 빈 바이트 문자열 b''을 반환한다.
>>> (lambda: _).__code__.co_lnotab
b''
이걸 다시 문자열로 변환하는 과정에서 최소 한 개 이상의 함수를 호출해야 하기 때문에 나는 빈 문자열을 다음과 같이 해결하기로 했다.
>>> chr(32)[1:]
''
1을 제외한 모든 숫자 리터럴 제거
문자열 리터럴을 제거하는데에서 그칠 수도 있었겠지만, 이왕 하는 김에 한단계 더 나아가보기로 했다. 컴퓨터에서는 모든 정보가 0과 1로 표현된다는 점에 착안해서 모든 숫자 리터럴을 1만 사용해서 표현하기로 했다.
1사이에 끼어있는 0은 다음과 같이 묵시적으로 표현될 수 있고 (0b1001),
(1 << 3) | 1
0은 다음과 같이 표현될 수 있다.
1 >> 1
1을 제외한 다른 숫자 리터럴은 사용하지 않기로 했기 때문에 1 << 3은 다음과 같이 바꾸도록 한다.
1 << 1 << 1 << 1
물론 다음과 같이 할 수도 있었겠지만, 나는 위의 표현이 조금 더 예술적(?)이라고 생각한다.
1 << (1 + 1 + 1)
이제 기본 재료가 마련되었으니, 모든 정수를 위와 같이 표현할 수 있는 함수를 만들어보자. 먼저, 원하는 개수만큼 1을 쉬프트 해주는 함수를 만들었다.
def gen_shift(n):
return '({})'.format(' << '.join(['1'] * (n + 1)))
하지만, Flake8 기준을 통과하기 위해서는 한줄당 80자 기준을 만족시켜야 하기 때문에 n이 충분히 크다면 줄바꿈을 해주어야 한다. 쉬프트 연산을 13번 하면 표현식의 문자열 길이가 68자가 된다. 거기에 들여쓰기 4칸, 앞에 붙을 수도 있는 + 연산자 등을 고려하여 쉬프트 연산을 13번 했다면 다음 줄로 넘어가도록 만들었다. 다소 지저분하지만, 최종 결과물을 깔끔하게 유지하기 위해 참고 넘어가기로 한다.
def gen_shift(n, threshold=13):
buf = []
while n > threshold:
buf.append(' << '.join(['1'] * (threshold + 1)))
buf.append('\n << ')
n -= threshold + 1
buf.append(' << '.join(['1'] * (n + 1)))
return '({})'.format(''.join(buf))
단 한번만 쉬프트 한다면,
>>> gen_shift(1)
'(1 << 1)'
14번 쉬프트 한다면,
>>> gen_shift(14)
'(1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1\n << 1)'
결과적으로 gen_shift(n)에서 생성된 표현식을 평가하면 과 같아야 한다.
>>> [eval(gen_shift(i)) == 2 ** i for i in range(15)]
[True, True, True, True, True, True, True, True, True, True, True, True, True, True, True]
이제 이것을 기반으로 정수를 쉬프트 연산식으로 인코딩 하는 함수를 만들 차례다.
def encode_num(n, prefix='', suffix='\n'):
buf, offset = [], 0
while n > 0:
if n & 1 != 0:
buf.append(gen_shift(offset))
n = n >> 1
offset += 1
return (suffix + prefix + '+ ').join(buf)
결과를 살펴보자면, 정수 5는 다음과 같이 변환된다.
>>> print(encode_num(5))
(1)
+ (1 << 1 << 1)
마찬가지로 정수 123은 다음과 같이 변환된다.
>>> print(encode_num(123))
(1)
+ (1 << 1)
+ (1 << 1 << 1 << 1)
+ (1 << 1 << 1 << 1 << 1)
+ (1 << 1 << 1 << 1 << 1 << 1)
+ (1 << 1 << 1 << 1 << 1 << 1 << 1)
이제 예술의 경지에 점점 다가가는듯한 모습이다.
Putting Everything Together
최대한 줄이고 줄여서 단 세개의 글로벌 함수만 코드에 노출할 수 있었다. 더 줄일 수 있었으면 좋겠지만, 지금 단계에선 내 능력 밖의 일인 것 같다.
_, __, C = getattr, globals, chr
그리고 글로벌 함수에 접근할 수 있는 함수를 만들었다.
T = lambda x: _(__()['__builtins__'], x)
이렇게 해서 다음과 같이 글로벌 함수를 호출할 수 있다.
T('float')('1.0')
T('map')(T('__import__'), ['subprocess', 'sys'])
위에서 설명했던 문자열을 정수로 인코딩 하는 함수를 다음과 같이 정의했다.
B = 256
J, L = (lambda _, __, ___: _(_, __, ___)), \
lambda _, __, ___: \
C(___ % __) + _(_, __, ___ // __) if ___ else \
C(1 << 1 << 1 << 1 << 1 << 1)[1:]
그러면 다음과 같이 정수로 인코딩 된 문자열을 디코딩 할 수 있다.
>>> J(L, B, 1986490977)
'argv'
지금 생각해보면 다음과 같이 정의해서 F(499850898534)처럼 간편하게 쓸 수도 있었을텐데 하는 아쉬움이 남는다.
F = lambda _: (lambda _, __, ___: _(_, __, ___))(
(lambda _, __, ___: \
C(___ % __) + _(_, __, ___ // __) if ___ else \
C(1 << 1 << 1 << 1 << 1 << 1)[1:]), \
1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1, _
)
어찌됐든 아래의 코드를
X, Y = T('map')(T('__import__'), ['subprocess', 'sys'])
다음과 같이 바꿀 수 있다.
X, Y = T(
J(L, B, 7364973),
)(T(
J(L, B, 450385647451203110002527),
), [
J(L, B, 545200826904043625543027),
J(L, B, 7567731),
])
한꺼번에 변환하기 쉽도록 코드 중간에 있는 정수 리터럴들을 한 곳에 모으자.
I = [
7364973,
450385647451203110002527,
545200826904043625543027,
7567731,
]
X, Y = T(
J(L, B, I[0]),
)(T(
J(L, B, I[1]),
), [
J(L, B, I[2]),
J(L, B, I[3]),
])
이제, 숫자 리터럴을 아름답게 변환해줄 차례이다. 모두 포함하기엔 코드가 너무 길어서 7364973의 경우만 살펴보도록 하겠다.
>>> print(encode_num(7364973))
(1)
+ (1 << 1 << 1)
+ (1 << 1 << 1 << 1)
+ (1 << 1 << 1 << 1 << 1 << 1)
+ (1 << 1 << 1 << 1 << 1 << 1 << 1)
+ (1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1)
+ (1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1)
+ (1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1
<< 1)
+ (1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1
<< 1 << 1 << 1 << 1 << 1 << 1 << 1)
+ (1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1
<< 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1)
+ (1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1
<< 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1 << 1)
그리고 배열의 인덱스도 같은 방식으로 변환해준다.
X, Y = T(
J(L, B, I[1 >> 1]),
)(T(
J(L, B, I[1]),
), [
J(L, B, I[1 << 1]),
J(L, B, I[1 + (1 << 1)]),
])
Just F***ing Around
거의 다 끝났다. 여기서 멈추기엔 무언가 아쉬워서 조금만 더 이상한 짓을 해보기로 했다. 다음과 같이 간단한 표현식의 경우 오른쪽 공간이 많이 남는다.
J(L, B, I[1 >> 1])
의미 없는 동작을 하는 코드로 빈 칸을 채워주자.
J(L, B, I[1 >> 1 << 1 >> 1 << 1 >> 1 << 1 >> 1 << 1 >> 1])
<< 1 >> 1 처럼 왼쪽으로 한칸 쉬프트 한 후에 다시 오른쪽으로 쉬프트 하는 코드도 괜찮고 * 1 처럼 항등원(identity element)을 곱해주거나, // 1 처럼 정수형 나눗셈 연산도 좋다.
Tips & Tricks
난독화 작업이라는 것이 아무래도 코드를 읽기 어렵게 만드는 과정이다보니 내 꾀에 내가 당하는 경우가 생길 수 있다. 그리고 위에서 설명한 난독화 과정을 거칠수록 코드를 읽는 난이도가 극악무도하게 올라가기 때문에 무언가를 바꿀때마다 기존의 기능들이 제대로 작동하는지 엄격하게 검증할 필요가 있다. 그래서 나는 코드를 변경할때마다 다음과 같은 명령어를 수행하면서 코드가 제대로 동작하는지 확인하고 넘어갔다.
flake8 calc.py && python3 test.py
맺음말
그렇게 해서 사람의 눈과 마음으로는 도저히 이해할 수도, 고칠 수도 없는 코드가 탄생했다. 일부만 발췌해보자면,
T(J(L, B, I[(1 << 1) + (1 << 1 << 1 << 1 << 1 << 1 >> 1 << 1 >> 1 * 1 * 1)]))(
T(J(L, B, I[(1 << 1 >> 1 << 1 >> 1 << 1 >> 1) + (1 << 1 << 1 << 1 << 1)]))(
_(_(R, J(L, B, I[(1 << 1) + (1 << 1 << 1) + (1 << 1 << 1 << 1 // 1)]))(
J(L, B, I[(1) + (1 << 1) + (1 << 1 << 1) + (1 << 1 << 1 << 1)])),
J(L, B, I[(1 << 1 << 1 << 1 << 1 << 1 >> 1 << 1 >> 1 // 1)]))()))
얼마나 아름다운가(!)
어떻게 하면 더 좋은 코드를 만들까 하는 고민은 많이 하지만, 어떻게 하면 더 ㅂㅅ같은 코드를 만들까 하는 고민은 평소에 거의 해볼 기회가 없다. 이번 대회를 통해 매우 색다른 즐거움을 향유할 수 있는 기회를 제공해주신 스포카 여러분들께 감사드린다.
그리고 다른 사람들이 작성한 흥미로운 코드도 있으니 한번 살펴보는걸 추천드린다.