anonymous?

입력 첫째줄: 테스트케이스 수 둘째줄: 한 줄에 있는 스티커 수 셋째줄: 스티커 별 점수 출력 각 테스트케이스에서 두 변을 공유하지 않는 스티커 점수의 최댓값 조건 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 됨 항상 S[0][0] 또는 S[1][0]부터 스티커를 떼기 시작함 -> S[0][0]을 뗄 때, S[1][0]을 뗄 때를 나누어서 점화식을 구현 항상 2 x n 배열로 스티커가 구성 풀이과정 예시를 통해 점화식을 생각해볼 수 있다. 스티커가 구성된 배열을 DP[2][5+1]라 하자. 편의 상 DP[0][0]과 DP[1][0]은 0으로 비워둔다. 그렇다면 DP[0][0] = DP[1][0] = 0으로 초기화를 하고, 나머지는 스티커 점수로 값을 채워야 한다. 0 50 10..

PROGRAMMING/Algorithm 2023. 7. 17. 00:00

배낭문제와 다이나믹 프로그래밍(DP)으로 생각하고 코드를 구현했다. 처음에 인사할 때 잃는 체력과 얻는 기쁨을 pair로 vector에 저장하고 남은 체력마다의 최대 기쁨도 vector에 저장했는데, 이때 vector에서 가져오고 저장하고 이런 처리하는 속도가 배열과 비교했을 때 상대적으로 너무 오래 걸리는 것 같았다. 그래서 잃는 체력과 얻는 기쁨은 1차원 배열에, 사람마다 남은 체력이 있을 때의 값을 최대 기쁨으로 저장하는 2차원 배열 DP를 이용해서 배낭 문제의 개념으로 문제를 풀었다. 인사하는 사람마다 남은 체력이 1~100일 때 인사했을 때 남은 체력이 0보다 크고 얻는 기쁨이 최대이면 이를 취하고, 그렇지 않으면 이전 사람에서의 해당 체력일 때를 취하였다. 처음에는 2차원 배열로 최대 기쁨을 ..

PROGRAMMING/Algorithm 2023. 7. 16. 15:50

BACKGROUND fuzzing 랜덤한 입력을 줘서 crash나 hang과 같은 런타임 상태를 모니터링하고 잠재적인 보안 취약점을 찾는 동적 취약점 탐지 기술 MOTIVATION 전통적인 입력 변형 방식에서의 입력 포맷에 맞는 입력 생성의 어려움 테스트케이스는 최소한으로 충족해야 할 포맷 형태가 있으며 포맷에 의존성이 높고 포맷 파서에 의해 체크를 통과되어야 타겟 프로그램에서 해당 입력으로 실행될 가능성이 있다.→ 신경망과 기계학습의 발전으로, 퍼징에서 입력 포맷을 충족하는 입력을 생성하는데 신경망이 적용되고 있다. → 생성모델은 타겟 프로그램의 복잡한 입력 포맷을 학습하는데 사용해서 잘 구성된 테스트케이스를 빠르게 생성 가능 → 전통적인 퍼징에서 테스트케이스 생성은 mutation 기반으로 이루어지며..

ANALYSIS/Paper Review 2023. 7. 11. 22:00

BACKGROUND Hybrid fuzzing fuzzing과 비교했을 때 hybrid fuzzing은 추가로 concolic execution(퍼징된 경로를 다시 가서 경로의 조건을 해결하고 새로운 경로를 시도하는 것)가 있다. 목표: 높은 기능(concolic execution으로 복잡한 조건을 풀어서 커버리지와 버그를 갖는)을 하는 시드를 알아내는 것 하이브리드 퍼저에서 제한된 시간에서 콘콜릭 실행을 효율적으로 사용하기 위한 시드를 추정하는 것이 중요 하이브리드 퍼징 흐름 언제 퍼저가 콘콜릭 엔진을 실행할지 모니터링 콘콜릭 실행에 사용되는 환경변수 설정 퍼저와 콘콜릭 실행기 사이에서 입력을 선택하고 필터링 휴리스틱 기반 시드 선택 방식 새로운 코드 커버리지에 도달하면서 작은 크기를 갖는 시드를 선호..

ANALYSIS/Paper Review 2023. 7. 11. 12:00

텐서(TENSOR) 배열(array)이나 행렬(matrix)과 유사한 특수한 자료구조 PyTorch에서는 텐서를 사용해서 모델의 입력(input)과 출력(output), 모델 매개변수들을 부호화(encode)함 GPU나 다른 하드웨어 가속기에서 실행 가능 텐서와 Numpy 배열은 동일한 내부(underly) 메모리를 공유할 수 있어 데이터를 복사할 필요없음 자동 미분(automatic differentiation)에 최적화됨 Dependency 추가 import torch import numpy as np 텐서(tensor) 초기화 1. 데이터로부터 직접(directly) 생성하기 data = [[1,2], [3,4]] x_data = torch.tensor(data) print(x_data) tenso..

PROGRAMMING/AI 2023. 7. 10. 23:24

BACKGROUND Fuzzing 랜덤 테스트 입력을 생성하고 생성한 입력으로 타겟 프로그램을 실행하여 잠재적 보안 취약점을 트리거한다. 퍼징의 단순성과 적은 성능 오버헤드로 리얼월드 프로그램의 다양한 취약점을 발견하는데 많이 사용해왔다. 퍼징에서의 최적화 문제 제한된 시간 동안 발견할 수 있는 취약점을 개수를 최대화하는 입력을 찾는 것이 목표 대부분의 퍼저는 코드 커버리지(ex. edge coverage)를 높여서 취약점을 발견할 가능성을 높이기 위해 가능한 많은 프로그램 코드를 실행함 퍼저에서 최적화 위해 진화 알고리즘 사용 코드 커버리지를 최대화하는 입력 생성하는 것 초기 시드 입력을 시작으로, 시드에 랜덤 변형을 가하면서 새로운 입력을 생성하고, 타겟 프로그램에 이 입력을 줘서 실행해서 유망한 입..

ANALYSIS/Paper Review 2023. 7. 10. 21:16

BACKGROUND 1. Greybox Fuzzing greybox fuzzing에서 새로운 입력은 mutation이나 crossover/splice를 통해 생성된다. (Seed Mutation) 생성된 입력은 fitness function에 의해 선택된다. (Seed Selection) 선택된 입력은 이후 mutation에서 사용하기 위해 seed pool에 넣는다. 이때 제한된 processing 능력 때문에 seed pool에 있는 아주 적은 시드만 선택되어서 다음 입력 mutation에 사용되기 위해 스케줄된다. 하나의 퍼저는 한 번에 하나의 시드만 스케줄링 할 수 있다. fitness function은 AFL에서 가장 많이 사용되는 것이 edge coverage이다. (새로운 branch에 도달..

ANALYSIS/Paper Review 2023. 6. 14. 01:16

BACKGROUND Fuzzing 타겟 프로그램에 많은 입력을 줘서 프로그램 예외를 분석하여 버그를 노출시키는 소프트웨어 테스트 기술 grey-box fuzzing 높은 효율성과 성능 Coverage-based grey-box fuzzing (CGF) 목표: 크래시를 더 많이 트리거하기 위해 코드 커버리지를 증가시킴 예시: AFL Directed grey-box fuzzing (DGF) 목표: 버그가 있는 코드 내 버그를 트리거하기 위한 입력 생성 랜덤 입력으로는 버그를 트리거 할 가능성이 낮기 때문에, DGF는 타겟 프로그램을 instrument하여 얻은 런타임 정보를 기반으로 버그 코드에 도달할 수 있는 입력을 생성 이미 알려진 취약점을 기반으로 PoC exploit을 생성하여 버그 코드에 적용하도록..

ANALYSIS/Paper Review 2023. 5. 14. 20:22

MOTIVATION 얼굴 영역 조작 시 컨텍스트는 그대로 두고 컨텍스트에 맞게 얼굴을 조정 → 조작 단서: **두 영역 사이 불일치** 겉으로 identity가 변경되는 얼굴 스왑으로 인한 얼굴 조작의 단서를 찾는 것 가설 A1. 얼굴 조작 방식은 얼굴의 내부 부분만 조작한다. 6가지 이미지 모두 얼굴은 조작되었지만 context는 그대로이다. (a), (b): 3D morphable model(3DMM)에 해당하는 영역, 즉 상단 이마 일부와 하단 턱 포함하는 얼굴 영역을 조작함 (c), (d): 정사각형 영역 조작 (e): 3DMM 기반 입 안쪽 부분을 제외한 얼굴 조작 (f): 얼굴 분할을 사용한 전체 얼굴 영역 조작 ⇒ Motivation 1: 이 얼굴 조작 방법 모두 머리 전체에는 영향을 주지 ..

ANALYSIS/Paper Review 2023. 4. 19. 11:25

Knapsack 알고리즘 DP[물건 번호][무게] = 최대 가치 -> 해당 물건에서 최대 무게를 가질 때 가질 수 있는 최대 가치에 해당 첫 번째 물건부터 무게 1부터 최대 무게 K까지 무게를 담았을 때 가질 수 있는 최대 가치를 DP에 저장한다. 이 정보는 다음 물건에서 최대 무게-다음 물건 무게가 이전에서 담을 수 있는 최대 무게에서 최대 가치를 가질 것이므로 이때의 가치와 다음 물건의 가치를 더했을 때와 이전 물건에서 최대 가치 중 최댓값을 취할 때 사용한다. 만약 i번째 물건의 무게가 최대 무게 j보다 작은 경우엔 담을 수 없으므로 i-1번째의 최대 무게 j에서의 최대 가치를 취한다. 최종적으로 마지막 물건에서 가질 수 있는 최대 무게에서의 최대 가치가 배낭에 넣을 수 있는 물건들의 가치합의 최댓..

PROGRAMMING/Algorithm 2023. 4. 14. 00:10

#include #include using namespace std; int main(){ int N,K; scanf("%d %d", &N, &K); vector sum(N+1,0); for(int m=0; m

PROGRAMMING/Algorithm 2023. 4. 11. 02:05

구간 합 알고리즘 사용 i~j 사이 합을 반복문을 사용할 때 시간복잡도는 O(n)인데, n이 클수록 시간복잡도가 커진다. 구간 합 알고리즘은 시간복잡도가 O(1) 먼저 현재 인덱스까지의 합을 sum[]에 저장한다. j-1까지의 총합 sum[j-1]에 j를 더하면 sum[j]이므로 sum[j] = sum[j-1] + arr[j] 만약 구간 [i,j]의 합을 구한다면 j까지의 합에서 i 이전까지의 합을 빼면 i부터 j까지의 합이므로 sum[j]-sum[i-1]으로 나타낼 수 있다. 계산의 편의를 위해 0번 인덱스는 0으로 초기화하고 사용하지 않고, 1번 인덱스부터 N까지 사용 #include #include #include using namespace std; int main(){ int N, M; scan..

PROGRAMMING/Algorithm 2023. 4. 11. 01:48