From patchwork Tue Jan 15 23:38:53 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Michael Niedermayer X-Patchwork-Id: 11765 Return-Path: X-Original-To: patchwork@ffaux-bg.ffmpeg.org Delivered-To: patchwork@ffaux-bg.ffmpeg.org Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org [79.124.17.100]) by ffaux.localdomain (Postfix) with ESMTP id E440144CD53 for ; Wed, 16 Jan 2019 01:40:05 +0200 (EET) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 0C33C68AAE8; Wed, 16 Jan 2019 01:39:54 +0200 (EET) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from vie01a-qmta-pe02-1.mx.upcmail.net (vie01a-qmta-pe02-1.mx.upcmail.net [62.179.121.181]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 9C4A368AA33 for ; Wed, 16 Jan 2019 01:39:47 +0200 (EET) Received: from [172.31.218.47] (helo=vie01a-dmta-pe06-2.mx.upcmail.net) by vie01a-pqmta-pe02.mx.upcmail.net with esmtp (Exim 4.88) (envelope-from ) id 1gjYJN-0000Za-EI for ffmpeg-devel@ffmpeg.org; Wed, 16 Jan 2019 00:40:01 +0100 Received: from [172.31.216.235] (helo=vie01a-pemc-psmtp-pe12.mail.upcmail.net) by vie01a-dmta-pe06.mx.upcmail.net with esmtp (Exim 4.88) (envelope-from ) id 1gjYJI-0001hA-0S for ffmpeg-devel@ffmpeg.org; Wed, 16 Jan 2019 00:39:56 +0100 Received: from localhost ([213.47.41.20]) by vie01a-pemc-psmtp-pe12.mail.upcmail.net with ESMTP id jYIJgSeBV2WSsjYIJgVihl; Wed, 16 Jan 2019 00:38:56 +0100 X-Env-Mailfrom: michael@niedermayer.cc X-Env-Rcptto: ffmpeg-devel@ffmpeg.org X-SourceIP: 213.47.41.20 X-CNFS-Analysis: v=2.3 cv=E7kcWpVl c=1 sm=1 tr=0 a=I1eytVlZLDX1BM2VTtTtSw==:117 a=I1eytVlZLDX1BM2VTtTtSw==:17 a=MKtGQD3n3ToA:10 a=1oJP67jkp3AA:10 a=GEAsPZ9sns4A:10 a=ZZnuYtJkoWoA:10 a=nZOtpAppAAAA:20 a=uemT7JB1B5AWIYjEQtQA:9 a=pHzHmUro8NiASowvMSCR:22 a=nt3jZW36AmriUCFCBwmW:22 From: Michael Niedermayer To: FFmpeg development discussions and patches Date: Wed, 16 Jan 2019 00:38:53 +0100 Message-Id: <20190115233853.9711-1-michael@niedermayer.cc> X-Mailer: git-send-email 2.20.1 MIME-Version: 1.0 X-CMAE-Envelope: MS4wfGgGbFHwTb3CmCP8e9uP2AKcvPfOrHyzoQwus1FtRrGIEeo+UXb3GLZ+D6APiYfVy2ENKqomYWoFTSgnnN4ZfSVT4IY3+koaCwAcP9zLPRsROmppDfTI nwbhkf0PJiCpGWoN1IZdD4HPMZMPli3u3WZ2yzIh2gVsQwTqITe2FfMq Subject: [FFmpeg-devel] [PATCH] avcodec/lagarith: Optimize case with singleton probability distribution X-BeenThere: ffmpeg-devel@ffmpeg.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: FFmpeg development discussions and patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: FFmpeg development discussions and patches Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" Fixes: Timeout Fixes: 10554/clusterfuzz-testcase-minimized-ffmpeg_AV_CODEC_ID_LAGARITH_fuzzer-5739938067251200 In case of a Denial of Service attack, the attacker wants to maximize the load on the target per byte transmitted from the attacker. For such a DoS attack it is best for the attacker to setup the probabilities so that the arithmetic decoder does not advance in the bytestream that way the attacker only needs to transmit the initial bytes and header for an arbitrary large frame. This patch here optimizes this codepath and avoids executing the arithmetic decoder more than once. It thus reduces the load causes by this codepath on the target. We also could completely disallow this codepath but it appears such odd probability distributions are not invalid. Before: Executed clusterfuzz-testcase-minimized-ffmpeg_AV_CODEC_ID_LAGARITH_fuzzer-5739938067251200 in 27400 ms After: Executed clusterfuzz-testcase-minimized-ffmpeg_AV_CODEC_ID_LAGARITH_fuzzer-5739938067251200 in 6676 ms Found-by: continuous fuzzing process https://github.com/google/oss-fuzz/tree/master/projects/ffmpeg Signed-off-by: Michael Niedermayer --- libavcodec/lagarith.c | 39 +++++++++++++++++++++++++++++++++++++++ libavcodec/lagarithrac.h | 1 + 2 files changed, 40 insertions(+) diff --git a/libavcodec/lagarith.c b/libavcodec/lagarith.c index 59169be5de..0dd9717266 100644 --- a/libavcodec/lagarith.c +++ b/libavcodec/lagarith.c @@ -175,6 +175,7 @@ static int lag_read_prob_header(lag_rac *rac, GetBitContext *gb) if (nnz == 1 && (show_bits_long(gb, 32) & 0xFFFFFF)) { return AVERROR_INVALIDDATA; } + rac->nnz = nnz; /* Scale probabilities so cumulative probability is an even power of 2. */ scale_factor = av_log2(cumul_prob); @@ -332,6 +333,44 @@ static int lag_decode_line(LagarithContext *l, lag_rac *rac, if (!esc_count) esc_count = -1; + // Detect a odd corner case which consumes disproportional computational + // resources in relation to the input size. We optimize this worst case + // to reduce its impact. + if (rac->nnz == 1) { + int v = -1; +handle_zeros1: + if (l->zeros_rem) { + int count = FFMIN(l->zeros_rem, width - i); + memset(dst + i, 0, count); + i += count; + l->zeros_rem -= count; + } + + while (i < width) { + if (v < 0) + v = lag_get_rac(rac); + + dst[i] =v; + ret++; + + if (v) + l->zeros = 0; + else + l->zeros++; + + i++; + if (l->zeros == esc_count) { + ret++; + + l->zeros = 0; + + l->zeros_rem = lag_calc_zero_run(v); + goto handle_zeros1; + } + } + return ret; + } + /* Output any zeros remaining from the previous run */ handle_zeros: if (l->zeros_rem) { diff --git a/libavcodec/lagarithrac.h b/libavcodec/lagarithrac.h index ee836d01db..9f37f3939c 100644 --- a/libavcodec/lagarithrac.h +++ b/libavcodec/lagarithrac.h @@ -47,6 +47,7 @@ typedef struct lag_rac { const uint8_t *bytestream; /**< Current position in input bytestream. */ const uint8_t *bytestream_end; /**< End position of input bytestream. */ + int nnz; int overread; #define MAX_OVERREAD 4