Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
Received-SPF: Pass (protection.outlook.com: domain of arm.com designates
 63.35.35.123 as permitted sender) receiver=protection.outlook.com;
 client-ip=63.35.35.123; helo=64aa7808-outbound-1.mta.getcheckrecipient.com;
Authentication-Results-Original: linux-foundation.org; dkim=none (message not
 signed) header.d=none;linux-foundation.org; dmarc=none action=none
 header.from=arm.com;
From:   Dave Rodgman <dave.rodgman@arm.com>
To:     akpm@linux-foundation.org
Cc:     nd@arm.com, dave.rodgman@arm.com, pushbx@ulukai.org, w@1wt.eu,
        sergey.senozhatsky.work@gmail.com, markus@oberhumer.com,
        minchan@kernel.org, ngupta@vflare.org, yuchao0@huawei.com,
        linux-kernel@vger.kernel.org
Subject: [PATCH] lib/lzo: fix ambiguous encoding bug in lzo-rle
Date:   Thu,  7 May 2020 11:02:03 +0100
Message-Id: <20200507100203.29785-1-dave.rodgman@arm.com>
Content-Transfer-Encoding: 8bit
Content-Type: text/plain
MIME-Version: 1.0
X-MS-Exchange-MessageSentRepresentingType: 1
Received: from davepc.cambridge.arm.com (217.140.106.49) by LNXP265CA0012.GBRP265.PROD.OUTLOOK.COM (2603:10a6:600:5e::24) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2979.28 via Frontend Transport; Thu, 7 May 2020 10:02:09 +0000
X-Mailer: git-send-email 2.23.0
X-ARM-No-Footer: FoSSMail
X-Originating-IP: [217.140.106.49]
X-MS-PublicTrafficType: Email
X-MS-Office365-Filtering-HT: Tenant
X-MS-Office365-Filtering-Correlation-Id: 1bf12398-9449-42d1-39be-08d7f26dbb0d
X-MS-TrafficTypeDiagnostic: DBBPR08MB4856:|DBBPR08MB4856:|VI1PR08MB4093:
X-MS-Exchange-Transport-Forked: True
X-Microsoft-Antispam-PRVS: <VI1PR08MB4093573B4444B2BAF45CF5948FA50@VI1PR08MB4093.eurprd08.prod.outlook.com>
x-checkrecipientrouted: true
NoDisclaimer: true
X-MS-Oob-TLC-OOBClassifiers: OLM:9508;OLM:9508;
X-Forefront-PRVS: 03965EFC76
X-MS-Exchange-SenderADCheck: 1
X-Microsoft-Antispam-Untrusted: BCL:0;
X-Microsoft-Antispam-Message-Info-Original: /v2wPM18UGnFtjiWsCJoxKQ4RA5dqQmGUVuPEJGHrCjsFgdwpH9sqrSEzIUcChVkJgVuwS24vohVuL8JevKnIraD9jyq+zX2tbY/921HCWIz8bEa7uRmVcQwhwsCFxrN/LZftP14/20MrD/iOS3eDEUxd204ydoxpGjOd3hrirwzLVo0rHhdlJkyS70UWtFFxdcuM01TM0MQgUmA8TFjgn6rcR737tM/TAS0y+M7C7MA11IfcFKX68q2eK20mTt+SEMPRk+ncA8L685FkqA2mNob662cFUl+FH5jSoYF2wwuCzQ4AdQHA7B/DQ6c58cFLUEjWu8oHhuitQWHwKKgdYcCjWQWRyvEzIV7T4QcopvCJrT0hVsRl6TM7p0Dg3qH4RRAPOGVQFTjXMiS8lhgGT/An6b2rcSMUcOK5xVUIKdnVUUh4tFFVu5XcuDl9DgEV8HyWvoVmb3E3xcNJy2UT+UcXUBCOcHi+FJtDc+H8RRIKnxGBiTRaQrlvsU9rUZzfKV10b2QaC6xuxe2ZO9elA==
X-Forefront-Antispam-Report-Untrusted: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:DBBPR08MB4661.eurprd08.prod.outlook.com;PTR:;CAT:NONE;SFTY:;SFS:(4636009)(346002)(136003)(39860400002)(376002)(396003)(366004)(33430700001)(86362001)(5660300002)(6666004)(316002)(186003)(6916009)(478600001)(16526019)(26005)(1076003)(6486002)(2906002)(66946007)(36756003)(4326008)(8676002)(7696005)(52116002)(83320400001)(83280400001)(66476007)(83310400001)(33440700001)(2616005)(83300400001)(44832011)(66556008)(956004)(83290400001)(8936002);DIR:OUT;SFP:1101;
X-MS-Exchange-AntiSpam-MessageData: I72Aa22l0KWspMqp+HhyM8CG49175JKfdV6KourwrS+xTJza/wfdsHZhJHmnCPnl8Og6ZknyHEV/EBWwkv9Nxl42V2ky6EfHnyfTTWBUy0/4Z+9nhXeFPUyqkT3gZ0Pyhbq8wEcGs+lXdJ+UOaqaZpexf5x2nA0aq2z+Bcdstm66/o7TQtHL9Nd+Hnzc7EUdFjJDWYEQsFFmh544rUbdEOzsr+nVF+TWnkxTkuQSn0hPklxxND5zsZPXxuF2laQymFFthkINA9RAxk3GwKzTvhsFZpHHXF6UUTiPbrMhcxPP6C4YFq3yAblxOP96DSOmJP63uqJcoOkCM0QHh9HDWNz0zBMYArnI1X9CCgrd/xGkdkThy7JBmHzApp7QztpUSA4sIkoQFe187+66+bVrwyFLOLjg+12KVQCNKwcNbpxzGFxmf8dsLQQgsV1rANtexL1oepxtrPafnshPpaIrdg9iXHFliG8erqmXdAU9Z3TMqiFst1L34xRk2TEo7Qqun2yTqMXF4s6bvuez4amKyROPSkC37NQVgsxHXPZBlp3r0AUPRtldnyA3iN6Su/nDKjuZ2Ndcii833uuV8HAavc1ENciYcxZ9jpo/jgYOlvymS8GPcucq2XrhiK9ouUL26J3bMcyvUeaz/9yw/pgS/S6l55rsjAHl2u/ZAuhm43GwBK1EYWQRodcYDgkEATTPFxTrr2Q/l3v8MHkDyIwkjGm33LFZsY6lZhDZfxYOPvoPwK+j/wDBQJK6DgU1gmLFTOrt3MrNbLRtcYUi6bBFspKhlS+2ucu+TRW0c5K2FT4=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DBBPR08MB4856
Original-Authentication-Results: linux-foundation.org; dkim=none (message not signed)
 header.d=none;linux-foundation.org; dmarc=none action=none
 header.from=arm.com;
X-EOPAttributedMessage: 0
X-MS-Exchange-Transport-CrossTenantHeadersStripped: VE1EUR03FT005.eop-EUR03.prod.protection.outlook.com
X-Forefront-Antispam-Report: CIP:63.35.35.123;CTRY:IE;LANG:en;SCL:1;SRV:;IPV:CAL;SFV:NSPM;H:64aa7808-outbound-1.mta.getcheckrecipient.com;PTR:ec2-63-35-35-123.eu-west-1.compute.amazonaws.com;CAT:NONE;SFTY:;SFS:(4636009)(39860400002)(396003)(136003)(376002)(346002)(46966005)(33430700001)(1076003)(956004)(34206002)(336012)(316002)(5660300002)(8936002)(33440700001)(4326008)(44832011)(81166007)(82310400002)(186003)(356005)(36906005)(2616005)(16526019)(2906002)(86362001)(6666004)(82740400003)(70206006)(478600001)(70586007)(26005)(6486002)(36756003)(47076004)(8676002)(7696005);DIR:OUT;SFP:1101;
X-MS-Office365-Filtering-Correlation-Id-Prvs: 556032e0-1775-4f6d-67ca-08d7f26db4d7
X-Forefront-PRVS: 03965EFC76
X-Microsoft-Antispam: BCL:0;
X-Microsoft-Antispam-Message-Info: fngRyj3I2eXMoVKKYQgSfMrQo0OQxWbOfc/BwkMw6M0i1/1LTUygO25Bgvf+P8K8x2dpyA769QoNnfcL3JUyTsMYJK1uaWcRSXGlodmdACMvUyIwJI/heP8y5zhcF1V9LXBf37N9K9k18wXgL3L5OexUlHtksJtru98dElaByLXps49J7wB1pkC/KTluYWb3/c8G16x9XhZvHXfz9EWDIibb+CJ/sIHhaVJBWVoBlL+ZzOEQDcMDos+uGDsQi/WQrmPplSNQLVp3L9rZ24ooFsA5H/m4HqYHnhvYuMR2ZGw+PLP6YVXSyCjArPMUadmZGqqumWWpUT1mZDMVCkwr3gDAeoinz2eCW8b8ArwJ7RQOSiVwqZC+l3l/x/51XF8UzXtb5Tmi4QBB88Nb8vMl1gkAqh6LtpKoFwKZ0cuqLc9znwffiqPDGzPrLp+kjzINO/EXXdGSB6iey4t/sBoHWEKG5tLxTfAoB4M38uIk/H8L1/dQKko1Ps0ohuqhx+vzkAxzO9kAlGcrKcTtqXDrWj3iKZztvD1ppiz79cIMxN/af8gF7cu8N4A8ZpUAdg+MQGsErO274/yu5gwW8dvuhg==
X-OriginatorOrg: arm.com
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 07 May 2020 10:02:19.8718
 (UTC)
X-MS-Exchange-CrossTenant-Network-Message-Id: 1bf12398-9449-42d1-39be-08d7f26dbb0d
X-MS-Exchange-CrossTenant-Id: f34e5979-57d9-4aaa-ad4d-b122a662184d
X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=f34e5979-57d9-4aaa-ad4d-b122a662184d;Ip=[63.35.35.123];Helo=[64aa7808-outbound-1.mta.getcheckrecipient.com]
X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem
X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR08MB4093
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

In some rare cases, for input data over 32 KB, lzo-rle could encode
two different inputs to the same compressed representation, so that
decompression is then ambiguous (i.e. data may be corrupted - although
zram is not affected because it operates over 4 KB pages).

This modifies the compressor without changing the decompressor or the
bitstream format, such that:
- there is no change to how data produced by the old compressor is
  decompressed
- an old decompressor will correctly decode data from the updated
  compressor
- performance and compression ratio are not affected
- we avoid introducing a new bitstream format

In testing over 12.8M real-world files totalling 903 GB, three files
were affected by this bug. I also constructed 37M semi-random 64 KB
files totalling 2.27 TB, and saw no affected files. Finally I tested
over files constructed to contain each of the ~1024 possible bad input
sequences; for all of these cases, updated lzo-rle worked correctly.

There is no significant impact to performance or compression ratio.

Cc: stable@vger.kernel.org
Signed-off-by: Dave Rodgman <dave.rodgman@arm.com>
---
 Documentation/lzo.txt    |  8 ++++++--
 lib/lzo/lzo1x_compress.c | 13 +++++++++++++
 2 files changed, 19 insertions(+), 2 deletions(-)

diff --git a/Documentation/lzo.txt b/Documentation/lzo.txt
index ca983328976b..f65b51523014 100644
--- a/Documentation/lzo.txt
+++ b/Documentation/lzo.txt
@@ -159,11 +159,15 @@ Byte sequences
            distance = 16384 + (H << 14) + D
            state = S (copy S literals after this block)
            End of stream is reached if distance == 16384
+           In version 1 only, to prevent ambiguity with the RLE case when
+           ((distance & 0x803f) == 0x803f) && (261 <= length <= 264), the
+           compressor must not emit block copies where distance and length
+           meet these conditions.
 
         In version 1 only, this instruction is also used to encode a run of
-        zeros if distance = 0xbfff, i.e. H = 1 and the D bits are all 1.
+           zeros if distance = 0xbfff, i.e. H = 1 and the D bits are all 1.
            In this case, it is followed by a fourth byte, X.
-           run length = ((X << 3) | (0 0 0 0 0 L L L)) + 4.
+           run length = ((X << 3) | (0 0 0 0 0 L L L)) + 4
 
       0 0 1 L L L L L  (32..63)
            Copy of small block within 16kB distance (preferably less than 34B)
diff --git a/lib/lzo/lzo1x_compress.c b/lib/lzo/lzo1x_compress.c
index 717c940112f9..8ad5ba2b86e2 100644
--- a/lib/lzo/lzo1x_compress.c
+++ b/lib/lzo/lzo1x_compress.c
@@ -268,6 +268,19 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 				*op++ = (M4_MARKER | ((m_off >> 11) & 8)
 						| (m_len - 2));
 			else {
+				if (unlikely(((m_off & 0x403f) == 0x403f)
+						&& (m_len >= 261)
+						&& (m_len <= 264))
+						&& likely(bitstream_version)) {
+					// Under lzo-rle, block copies
+					// for 261 <= length <= 264 and
+					// (distance & 0x80f3) == 0x80f3
+					// can result in ambiguous
+					// output. Adjust length
+					// to 260 to prevent ambiguity.
+					ip -= m_len - 260;
+					m_len = 260;
+				}
 				m_len -= M4_MAX_LEN;
 				*op++ = (M4_MARKER | ((m_off >> 11) & 8));
 				while (unlikely(m_len > 255)) {
-- 
2.23.0