Java Puzzle 4: Liquid

Mar 08, 2012

Can you program your way past airport security? The usual rules apply.

No liquids are allowed in your hand luggage:

package liquid;

import java.lang.String;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;

public class Luggage {
    private final Collection<String> items;

    public Luggage(Collection<String> items) {
        items = Collections.unmodifiableCollection(new ArrayList<String>(items));
        for (String item : items) {
            if (item.contains("liquid")) {
                throw new SecurityException("No liquids allowed in your hand luggage!");
            }
        }
        this.items = items;
    }

    public Collection<String> getItems() {
        return items;
    }

    public void fly() {
        if (items.contains("liquid water")) {
            // The goal is to reach this line
            System.out.println("Oh no, water on a plane! We're all going to die!");
        }
    }
}

Can you, as a thirsty passenger, take some water with you anyways? ~~Leave your answer in a comment. The comments will stay private for a while, and be published later in the next blog post.~~. Try to solve it, and then look at the solutions in the comments below!

~~Update: comments were briefly not moderated, already showing the solution immediately; sorry for that.~~
Update: Let's try to do it differently from the other puzzles then! Only look at the comments below after you're tried to solve it yourself!

20 comments

Wouter wrote on 2012-03-08 13:00

Spoiler alert: solutions are in the comments below. Don't look at them if you want to try it yourself!

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

Oliver Pfeiffer wrote on 2012-03-08 14:15

This should work, since the array is reused if it is instanceof Object[] …

private static Object[] array;

public static void main(String[] args) {
    Collection items = new ArrayList() {
        @Override
        public Object[] toArray() {
            return array = super.toArray();
        }
    };
    items.add("42");
    Luggage luggage = new Luggage(items);
    array[0] = "liquid water";
    luggage.fly();
}

Gauthier JACQUES wrote on 2012-03-08 14:16

Here it is

    public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
        WeirdList<String> mysStuff = new WeirdList<String>(Arrays.asList("All my stuff"));
        Luggage luggage = new Luggage(mysStuff);
        mysStuff.getCurrentObjs()[0] = "liquid water";
        luggage.fly();
     }

    private static class WeirdList<E> extends ArrayList<E> {
        private Object[] currentObjs;

        private WeirdList(Collection<? extends E> c) {
            super(c);
        }

        @Override
        public Object[] toArray() {
            currentObjs = super.toArray();
            return currentObjs;
        }

        public Object[] getCurrentObjs() {
            return currentObjs;
        }
    }

Ives wrote on 2012-03-08 14:17

This one is not so hard. The trick is that the ArrayList constructor calls toArray() on the original collection and uses that result as a backing array. With some simple code, we can get hold of that array and modify it after the security check.

package liquid;

import java.util.ArrayList;

public class Passenger
{
    public static void main(String[] args)
    {
        UnsafeLuggage ul = new UnsafeLuggage();
        ul.add("socks");

        Luggage luggage = new Luggage(ul);
        ul.array[0] = "liquid water";

        luggage.fly();
    }

    static class UnsafeLuggage extends ArrayList<String>
    {
        public Object[] array;

        @Override
        public Object[] toArray()
        {
            array = new Object[size()];
            toArray(array);
            return array;
        }
    }
}

Praveen wrote on 2012-03-16 14:11

Good explanation!

Thomas wrote on 2012-03-08 14:26

All you need is a class implementing the Collection interface whose return value of toArray() is under your control. For shortness I used ArrayList as a base class instead of implementing all the methods of the Collection interface myself.

package liquid;

import java.util.ArrayList;

public class Thirsty {

    public static void main(String[] args) {
        final Object[] data = new Object[] { "socks" };
        Luggage l = new Luggage(new ArrayList<String>() {
            @Override
            public Object[] toArray() {
                return data;
            }
        });
        data[0] = "liquid water";
        l.fly();
    }
}

Marc wrote on 2012-03-08 14:43

I did almost the same as Ives, but by creating a Collection that replaces instead of adds.

package challenge4;

import java.util.ArrayList;
import java.util.Collection;

public class Main {
    public static void main(String[] args) {
        Collection<String> items = new ArrayList<String>() {
            private Object[] elems = new Object[1];

            @Override
            public boolean add(String e) {
                elems[0] = e;
                return true;
            }

            @Override
            public int size() {
                return 1;
            }

            @Override
            public Object[] toArray() {
                return elems;
            }
        };
        items.add("nothing");
        Luggage luggage = new Luggage(items);
        items.add("liquid water");
        luggage.fly();
    }
}

Sean Reilly wrote on 2012-03-08 14:47

You can exploit the fact that ArrayList reuses the object array generated by the Collection passed into its constructor.

This allows you to modify the contents of the arraylist after it has been created (although i don’t think you can change its size using this approach).

package liquid;

import java.util.ArrayList;

public class Main {
    public static void main (String... args) {
        EvilList evil = new EvilList();
        evil.add("harmless item");

        Luggage luggage = new Luggage(evil);
        evil.generatedArray[0] = "liquid water";
        luggage.fly();
    }

    public static class EvilList extends ArrayList<String> {

        public Object[] generatedArray;

        @Override
        public Object[] toArray() {
            generatedArray = super.toArray();
            return generatedArray;
        }
    }
}

Paul Macdona wrote on 2012-03-08 14:56

Better watch out for evil luggage collections fiddling with your arrays…

public class Passenger
{
    public static void main(final String[] args)
    {
        new Passenger().board();
    }

    public void board()
    {
        EvilCollection<String> evilLuggage = new EvilCollection<String>();
        evilLuggage.add("cheeseburgers");

        Luggage luggage = new Luggage(evilLuggage);
        evilLuggage.array[0] = "liquid water";

        luggage.fly();
    }

    class EvilCollection<T> extends ArrayList<T>
    {
        public Object[] array;

        @Override
        public Object[] toArray()
        {
            array = new Object[size()];
            return toArray(array);
        }
    }
}

David Shay wrote on 2012-03-08 15:27

The joy of Serialization!

import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.ObjectOutputStream;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

public class Traveller {
    private static List internalList;

    public static void main(String[] args) throws IOException {
        List items = new ArrayList();
        items.add("not water");
        Luggage luggage = new Luggage(items);
        Collection luggageItem = luggage.getItems();

        ObjectOutputStream oos = new ObjectOutputStream(new ByteArrayOutputStream()) {
            {
                enableReplaceObject(true);
            }
            @Override
            protected Object replaceObject(Object obj) throws java.io.IOException {
                if (obj instanceof ArrayList) {
                    internalList = (List) obj;
                }

                return obj;
            }
        };

        oos.writeObject(luggageItem);

        internalList.add("liquid water");

        luggage.fly();
    }
}

Wouter wrote on 2012-03-08 16:32

Does this work for you with the security manager enabled? enableReplaceObject requires a specific permission!

Gaël Renoux wrote on 2012-03-08 16:17

I erred on the complicated side I guess, as I completely defined a dirty implementation of the Collection interface. The tricky bit was that toArray must return an Object[], not a String[], for the ArrayList constructor to use it.

deadalnix wrote on 2012-03-08 16:24

package liquid;

import java.util.ArrayList; import java.util.Collection;

public class Main { public static void main(String[] argv) { Object[] magicLuggagesContent = { “solid water” };

    Collection items = new MagicLuggages(magicLuggagesContent);

    Luggage luggage = new Luggage(items);
    magicLuggagesContent[0] = "liquid water";

    luggage.fly();
}

static class MagicLuggages extends ArrayList {

    private static final long    serialVersionUID    = -9010203348684151355L;

    Object[]                    data;

    MagicLuggages(Object[] data) {
        this.data = data;
    }

    @Override
    public Object[] toArray() {
        return data;
    }
} }

This is implementation dependent, but works.

Marc Fortin wrote on 2012-03-08 16:30

Easy one :

package liquid;

import java.util.ArrayList;

public class Main {

    private static Object[] objs;

    public static void main(String[] args) {
        BadList<String> l = new BadList<String>();

        Luggage f = new Luggage(l);

        objs[0] = "liquid water";

        f.fly();

    }

    private static class BadList<E> extends ArrayList<E> {
        public  Object[] toArray() {
            Object[] obj = new Object[1];
            obj[0] = "";
            objs = obj;
            return obj;
        }
    }
}

mbartmann wrote on 2012-03-08 17:11

package you;

import java.util.ArrayList;

import liquid.Luggage;

public class Passenger { public static void main( String[] args ) throws Exception { final Object[] a = new Object[]{“ice”}; Luggage luggage = new Luggage( new ArrayList() { @Override public Object[] toArray() { return a; } }); a[0] = “liquid water”; luggage.fly(); } }

Jonathan Fisher wrote on 2012-03-08 18:37

My first attempt… hide the data in secret compartment, then after the security checkpoint, hijack and innocently looking method to add it back to the luggage. But, the Luggage.class defeats this by wrapping my collection.

I haven’t read the solution yet, not giving up quite yet!

    public static void main(String[] args) {
        Collection<String> items = new ArrayList<String>() {
            @Override
            public Iterator<String> iterator() {
                this.add("liquid water");
                return super.iterator();
            }
        };
        items.add("pancakes");

        Luggage lug = new Luggage(items);

        lug.getItems().iterator();
        lug.fly();
    }

Jonathan Fisher wrote on 2012-03-08 19:46

So looking for a better method to override, I looked at the source for ArrayList:

    public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

But, for whatever reason, ArrayList.toArray is smart enough to not allow someone control over it’s own array:

    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

So all I have to do is override toArray:

    public static void main(String[] args) throws Exception {
        final Object[] myArray = new Object[] { "Nothing to see here..." };

        ArrayList<String> items = new ArrayList<String>(1) {
            private static final long serialVersionUID = 8683452581122892189L;

            @Override
            public Object[] toArray() {
                return myArray;
            }
        };

        Luggage lug = new Luggage(items);
        myArray[0] = "liquid water";
        lug.fly();
    }

This probably should be a bug in the JDK. I don’t think ArrayList should allow anyone control over it’s state!

Mohamed wrote on 2012-03-08 20:06

public static void main(String[] args) { final Object[] data = new Object[]{“”}; Luggage l = new Luggage(new ArrayList(){ @Override public Object[] toArray() { return data; } }); data[0] = “liquid water”; l.fly(); }

Wouter wrote on 2012-03-08 20:22

I prepared this as a separate blog-post, but given my missing-moderation-fluke (or is it actually better this way?), I’ll just add it here as a comment:

For those breaking their head over it: the for-loop, the Collection.contains and String.contains were just distractions to avoid making it too easy. Collections.unmodifiableCollection is also still perfectly safe. The hole is in the ArrayList constructor. It’s implemented like this (in JDK 6 and 7):

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

There’s a check if the array returned from c.toArray() is of the right type. But nothing makes sure c doesn’t still hold a reference to that array. So the ArrayList can still be modified from the inside by modifying the array directly.

We create some perfectly safe luggage, and then teleport our water in:

final Object[] items = {"toothbrush"};

Luggage luggage = new Luggage(new ArrayList<String>() {
    @Override public Object[] toArray() {
        return items;
    }
});

items[0] = "liquid water";
luggage.fly();

Conclusion: You’ll often see code code creating a defensive copy with new ArrayList<>(items), but in fact it’s not a completely safe copy. This is officially not a bug.

That’s not going to stop me from still using it though – it’s still good enough for all non-security-sensitive code.

Ives wrote on 2012-03-08 20:37

The two contains() calls and the getItems() method did indeed distract me initially.

And since you’re asking: I preferred the previous format where comments were hidden until the solution is revealed.

deadalnix wrote on 2012-03-09 10:22

I confirm this :D I looked at this to begin with.

And hiding comment is better as well.

mbartmann wrote on 2012-03-09 14:51

Where is the water? :-)

Wouter wrote on 2012-03-09 17:26

Oops, I just teleported it into my comment :)

Heinz Kabutz wrote on 2012-03-09 11:39

Well, again I have learned something new:

package liquid;

import java.util.*;

public class OlympicAir {
  public static void main(String[] args) {
    MyArrayList items = new MyArrayList();
    Luggage luggage = new Luggage(items);
    System.out.println(luggage.getItems());
    items.objects[2] = "liquid water";
    System.out.println(luggage.getItems());
    luggage.fly();
  }
  private static class MyArrayList extends ArrayList<String> {
    public Object[] objects = {
        "gun", "brick", "nuclear waste"
    };
    public Object[] toArray() {
      return objects;
    }
  }
}

Manuel Verriez wrote on 2012-03-09 13:16

To discover method(s) from original list that were called and that we could exploit, I used dynamic proxy API. Here is my solution:

package liquid;

import java.lang.reflect.InvocationHandler;
import java.lang.reflect.Method;
import java.lang.reflect.Proxy;
import java.util.ArrayList;
import java.util.List;


public class Pax {

    public static void main(String args[]){

        Object[] samFisher = new Object[]{"brush", "purse"};
        List<String> list = new ArrayList<String>();
        Handler handler = new Handler(list, samFisher);
        Class[] interfacesArray = new Class[] {List.class};
        List items = (List) Proxy.newProxyInstance(ArrayList.class.getClassLoader(), interfacesArray, handler);
        Luggage luggage = new Luggage(items);
        samFisher[0] = "liquid water";
        luggage.fly();
    }

    public static class Handler implements InvocationHandler {

        private List myList;
        private Object[] obj ;

        public Handler(List list, Object[] object) {
            this.myList = list;
            this.obj = object;
        }

        public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
            try {
                System.out.println("Method called : " + method.getName());
                if ("toArray".equals(method.getName())){
                    return this.obj;
                }
                return method.invoke(myList, args);
            } catch ( Exception e ) {
                return new ArrayList();
            }
        }
    }
}

Jonathan Fisher wrote on 2012-03-09 18:57

Definitely the most unique solution here, props! :)

But will this run with the security manager enabled?

Manuel Verriez wrote on 2012-03-10 15:48

Yes, dynamic proxy can be used with -Djava.security.manager paramter.

Algirdas & Ricardas wrote on 2012-03-09 18:15

package me;

import java.util.ArrayList;

import liquid.Luggage;

public class LiquidLover {

    public static void main(String[] args) {
        final Object[] data = new Object[] {"water"};
        ArrayList<String> items = new ArrayList<String>() {
            @Override
            public Object[] toArray() {
                return data;
            }
        };
        Luggage luggage = new Luggage(items);
        data[0] = "liquid water";
        luggage.fly();
    }
}

Mike Thompson wrote on 2012-03-10 03:16

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package sneaky;

import java.util.*;
import liquid.*;

public class Passenger {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        final Object[] compartments = { "harmless stuff" };
        final Collection<String> stuff = new AbstractCollection<String>() {
            @Override
            public Object[] toArray() {
                return compartments;
            }

            @Override
            public Iterator<String> iterator() {
                throw new UnsupportedOperationException("Not supported yet.");
            }

            @Override
            public int size() {
                throw new UnsupportedOperationException("Not supported yet.");
            }

        };

        final Luggage bag = new Luggage(stuff);
        compartments[0] = "liquid water";
        bag.fly();
    }
}