Help with a Java Puzzle.

[DaLoverhino]

Hello I am reading Java Programming Language 3rd Edition as a self
study and I'm stuck with the following on Chap 3, exercise 11:

Find at least one security hole in SortDouble that would let a sorting
algorithm cheat on its metrics without getting caught. Fix the
security hole. Assume that the sorting algorithm author doesn't get to
write main.


My answer: Well, the only thing I can think of is that the extended
class of SortDouble could probe() for all the values[] in SortDouble,
and then it could swap and compare without having to use SortDouble's
routines, and thus not get audited. After that, it could do a few
calls to SortDouble's swap and compare methods to make the numbers look
alright.

Anyways, I don't think that is the answer that JPL is looking for. I'm
thinking they are looking for something more language specific.

My next guess would be that values is not made final, and some how you
can trick SortDouble, but I can't think of anything.

My next guess is that somehow you can clone SortDouble, and have the
clone do all the work, but SortDouble doesn't implement Cloneable. So,
I don't see how that could be a security risk.

My next guess is that somehow you can do a trick in the extended
classes constructor. Perhaps, the extended classes constructor has
only one constructor that requires you to pass the double[] array.
And, then you can do all your work in that... don't really know....

Could someone help me out? Thanks.



Here's the sample code in the book:

/*** SortDouble.java */
abstract class SortDouble {

private double[] values;
private final SortMetrics curMetrics = new SortMetrics();

/** Invoked to do the full sort */
public final SortMetrics sort( double[] data) {
values = data;
curMetrics.init();
doSort();
return getMetrics();
}

public final SortMetrics getMetrics() {
return (SortMetrics) curMetrics.clone();
}


/** For extended classes to know the number of elements */
protected final int getDataLength() {
return values.length;
}


/** For extended classes to probe elements */
protected final double probe( int i) {
curMetrics.probeCnt++;
return values;
}


/** For extended classes to compare elements */
protected final int compare( int i, int j) {
curMetrics.compareCnt++;
double d1 = values;
double d2 = values[j];
if( d1 == d2)
return 0;
else
return ( d1 < d2 ? -1 : 1);
}


/** For extended classes to swap elements */
protected final void swap( int i, int j) {
curMetrics.swapCnt++;
double tmp = values;
values = values[j];
values[j] = tmp;
}

/** Extended classes implement this -- used by sort */
protected abstract void doSort();
}


/*** SimpleSortDouble.java */

class SimpleSortDouble extends SortDouble {
protected void doSort() {
for( int i = 0; i < getDataLength(); ++i) {
for( int j = i + 1; j < getDataLength(); ++j) {
if( compare(i,j) > 0)
swap(i,j);
}
}
}
}


/*** SortMetrics.java */

final class SortMetrics implements Cloneable {
public long probeCnt, // simple data probes
compareCnt, // comparing two elements
swapCnt; // swapping two elements

public void init() {
probeCnt = swapCnt = compareCnt = 0;
}

public String toString() {
return probeCnt + " probes " +
compareCnt + " compares " +
swapCnt + " swaps";
}

/** This class supports clone */
public Object clone() {
try {
return super.clone(); // default mechanism works
}
catch( CloneNotSupportedException e) {
// can't happen: this and Object both clone
throw new InternalError( e.toString());
}
}
}


/*** TestSort.java */
public class TestSort {
static double[] testData = {
0.3, 1.3e-2, 7.9, 3.17 };

public static void main( String[] args) {
SortDouble bsort = new SimpleSortDouble();
SortMetrics metrics = bsort.sort(testData);
System.out.println( "Metrics: " + metrics);
for( int i = 0; i < testData.length; ++i)
System.out.println( "\t" + testData);
}
}

 

[Oliver Wong]

Hello I am reading Java Programming Language 3rd Edition as a self
study and I'm stuck with the following on Chap 3, exercise 11:

Find at least one security hole in SortDouble that would let a sorting
algorithm cheat on its metrics without getting caught. Fix the
security hole. Assume that the sorting algorithm author doesn't get to
write main.

My answer: Well, the only thing I can think of is that the extended
class of SortDouble could probe() for all the values[] in SortDouble,
and then it could swap and compare without having to use SortDouble's
routines, and thus not get audited. After that, it could do a few
calls to SortDouble's swap and compare methods to make the numbers look
alright.

This is the answer I'm thinking of as well. Unfortunately, there's no
way to fix this hole that I can think of without a very major redesign of
the entire architecture (essentially the extending class would have to
provide method delegates, and would never actually get to see the data, i.e.
no probe() method). Of course, if you're willing to use reflection, you can
actually gain access to private member variables, but I don't think this is
what the exercise expects you to do. Similarly, you could use JNI to execute
C code to hack at the virtual machine actually running your program, but
again, I don't think this is what it means either.

My next guess would be that values is not made final, and some how you
can trick SortDouble, but I can't think of anything.

Although the values aren't final, they are declared as being private,
meaning the underlying algorithm can't access them (unless using reflection
or JNI as mentioned above).

My next guess is that somehow you can clone SortDouble, and have the
clone do all the work, but SortDouble doesn't implement Cloneable. So,
I don't see how that could be a security risk.

When you extend SortDouble, your new class could implement Cloneable.
Eventually though, you'd just be doing the same trick as your original
solution; that is, you'd have to inspect the results from your clone, and
then sort your own local data without doing any probes().

My next guess is that somehow you can do a trick in the extended
classes constructor. Perhaps, the extended classes constructor has
only one constructor that requires you to pass the double[] array.
And, then you can do all your work in that... don't really know....

Since you don't get to change main, your constructor needs to also take
in zero arguments. As such, you don't yet have access to the data you need
to sort.

[code snipped]

- Oliver

 

[Roedy Green]

My next guess is that somehow you can do a trick in the extended
classes constructor. Perhaps, the extended classes constructor has
only one constructor that requires you to pass the double[] array.
And, then you can do all your work in that... don't really know....

He is not measuring speed, but number of compares and number of swaps
as though all other overhead of the sort were inconsequential.

What if compare sorted in reverse order or something totally bizarre,
like the nth random off a seed? You still need the compare method to
determine order.

You can't override the methods.
You can't jiggle the private counters back.

At first I thought I could cheat this way:

sort calls your doSort which is turn recursively calls sort
with some dummy data. That gives you a handle to the SortMetrics
object. You can now fiddle the numbers in it any time you want.

However, this does not work since doSort gets only a clone of the
master object, not the master SortMetrics object.

I don't know if Reflection is considered an option at this stage in
your textbook. You can do bloody well anything you want if you allow
it.

Here is another idea. Your sort simply calls itself or another entry
point to itself to sort the data. Doing this creates a new Metrics .
Then it throws away the metrics. It can then do a few dummy calls to
update the real metrics to look plausible. I'll leave you to work out
the details. It may have to create a second SimpleSortDouble object.

 

[pkriens]

Trivial:

/*** SimpleSortDouble.java */

class SimpleSortDouble extends SortDouble {
protected void doSort() {
for( int i = 0; i < getDataLength(); ++i) {
for( int j = i + 1; j < getDataLength(); ++j) {
if( compare(i,j) > 0)
swap(i,j);
}
}
super.sort(new double[0]);
}

Removing the init method solves the problem.


}

 

[Chris Uppal]

Hello I am reading Java Programming Language 3rd Edition as a self
study and I'm stuck with the following on Chap 3, exercise 11:

Find at least one security hole in SortDouble that would let a sorting
algorithm cheat on its metrics without getting caught. Fix the
security hole. Assume that the sorting algorithm author doesn't get to
write main.


My answer: Well, the only thing I can think of is that the extended
class of SortDouble could probe() for all the values[] in SortDouble,
and then it could swap and compare without having to use SortDouble's
routines, and thus not get audited. After that, it could do a few
calls to SortDouble's swap and compare methods to make the numbers look
alright.

Yes, that would work.

Anyways, I don't think that is the answer that JPL is looking for. I'm
thinking they are looking for something more language specific.

I agree. I have a better "cheat" (below), but it still doesn't feel as if it's
the right answer. But then, as far as I can see the authors have closed all
the language specific loopholes (short of using reflection or JNI as Oliver
suggested), so it's the best I can think of.

My next guess would be [...]

I don't believe that any of the snipped methods would work.

But how about this ?

class CheatingSortDouble
extends SortDouble
{
private boolean inSortAlready = false;
protected void
doSort()
{
if (inSortAlready)
return;
reallySort();
inSortAlready = true;
sort();
inSortAlready = false;
}

private void
reallySort()
{
... any handy sorting code...
}
}

The recursive call to sort() will result in curMetrics being re-init()-ed, thus
setting all the counts to zero.

-- chris

 

[Chris Uppal]

Trivial:

Not that trivial.

super.sort(new double[0]);

Goes into an infinite loop since "super" only affects the choice of sort()
implementation (there's only one possibility in this case so "super" is
entirely redundant), not the calls issued /from/ that method.

Also passing new double[0] as the parameter will cause the 'values' field to be
updated, and that would show up in the test output. I think you have to create
a new copy of values (using probe()) and pass that (which I completely failed
to do in my own "solution").

-- chris

 

[pkriens]

Ok, I forgot to check if I am inside (ie. getDataLength() ==0), but
that was left as an
exercise to the reader

BTW, the values field is updated, but it is private. The main method
prints out the
array it gave as a parameter. So that is not an argument.

So 0 points for coding, 10 points for finding the weak spot?

Event better is:

class SimpleSortDouble extends SortDouble {
protected void doSort() {
for( int i = 0; i < getDataLength(); ++i) {
for( int j = i + 1; j < getDataLength(); ++j) {
if( compare(i,j) > 0)
swap(i,j);
}
}
try { super.sort(null); } catch(Throwable skipping) {}
}
}

Finally a case where skipping the exception makes sense!
And I like the super as documentation! Puh!


Output (To prove it runs):

Metrics: 0 probes 0 compares 0 swaps
0.013
0.3
3.17
7.9

Just ran it in Eclipse to test (whcih I should have done the first time)

 

[DaLoverhino]

Hello guys (and gals).

Thanks for the helpful responses. I like the re-init solution, and
ignoring exception solution. I think they both are the language
specific tricks the authors, Ken Arnold, James Gosling, and David
Holmes were looking for.

I'm wondering about the exception solution, since the exercise is only
on chapter 3, and exceptions were only covered briefly in chapter 1 as
part of an overview of the Java language. But the exercise did say "at
least one", so there must be plenty, and I think your solutions were
awesome.

Thanks.

 

[DaLoverhino]

Well, for completeness sake, I decided to post the cheat (solution)
code suggested by you guys:

/*** CheatSortDouble.java */

class CheatSortDouble extends SortDouble {
boolean is_calledOnce = false;

protected void doSort() {
double[] array = new double[0];


if( is_calledOnce == false) {
is_calledOnce = true;
slowBubbleSort();
super.sort(array);
}
return;
}



private void slowBubbleSort() {
for( int i = 0; i < getDataLength(); ++i) {
for( int j = i + 1; j < getDataLength(); ++j) {
if( compare(i,j) > 0)
swap(i,j);
}
}
}
}



Here's my solution to fixing it, assuming we don't have to worry about
multithreading. I'm wondering what you guys think about the code
below. The main change is to add a boolean which gets set in the
sort() function that prevents recursively calling the sort() function.
If a recursive call is made, an exception is thrown. I'm wondering
what you guys think of it. Thanks again.

/*** CheatSortDouble.java */

class CheatSortDouble extends SortDouble {
boolean is_calledOnce = false;

protected void doSort() {
double[] array = new double[0];


if( is_calledOnce == false) {
is_calledOnce = true;
slowBubbleSort();
super.sort(array);
}
return;
}



private void slowBubbleSort() {
for( int i = 0; i < getDataLength(); ++i) {
for( int j = i + 1; j < getDataLength(); ++j) {
if( compare(i,j) > 0)
swap(i,j);
}
}
}
}

 

[Oliver Wong]

Here's my solution to fixing it, assuming we don't have to worry about
multithreading. I'm wondering what you guys think about the code
below. The main change is to add a boolean which gets set in the
sort() function that prevents recursively calling the sort() function.
If a recursive call is made, an exception is thrown. I'm wondering
what you guys think of it. Thanks again.

[code snipped]

I didn't see your solution for fixing it; I only saw your solution for
"cheating" again.

Anyway, there's two main ways I can think of to fix this. The first is
similar to your boolean idea: Make the class be immutable after the first
call to sort(). That is, the first time sort() is called, the sorting
algorithm is done, and the metrics calculated and returned. The metrics is
also cached. Every subsequent call to sort doesn't re-perform the sorting,
but instead just returns the cached metrics.

The second is to not make Metrics be an instance variable (which would
require removing the getMetrics() method). Instead, make Metrics a local
variable of sort(), which gets returned. The only way to get metrics is to
actually perform a sort, and if the client doesn't save the metrics after a
call to sort, the metrics are lost forever, to be garbage collected.

- Oliver

 

[DaLoverhino]

I like your second solution, but there's no danger of recursively
calling sort() method?

Anyways, here's my solution. I actually have it so that they can call
sort() and it will resort. It just prevents recursively calling the
function. I just thought resorting by instantiating a new object would
be too restrictive in the 'real world', (of course, in the real world,
I'd also worry about multi-threading.)


thanks for your feedback.



/*** SortDouble.java */
abstract class SortDouble {

private double[] values;
private final SortMetrics curMetrics = new SortMetrics();
private boolean is_sorting = false;

/** Invoked to do the full sort */
public final SortMetrics sort( double[] data) {

if( !is_sorting) {
is_sorting = true;
values = data;
curMetrics.init();
doSort();
is_sorting = false;

}
else {
throw new IllegalStateException( );
// Not allowed to call sort() recursively.
// This is to prevent doSort() calling sort()
// with an empty data[] array which will cause
// curMetrics to have 0's for metrics.
}


return getMetrics();
}

public final SortMetrics getMetrics() {
return (SortMetrics) curMetrics.clone();
}


/** For extended classes to know the number of elements */
protected final int getDataLength() {
return values.length;
}


/** For extended classes to probe elements */
protected final double probe( int i) {
curMetrics.probeCnt++;
return values;
}


/** For extended classes to compare elements */
protected final int compare( int i, int j) {
curMetrics.compareCnt++;
double d1 = values;
double d2 = values[j];
if( d1 == d2)
return 0;
else
return ( d1 < d2 ? -1 : 1);
}


/** For extended classes to swap elements */
protected final void swap( int i, int j) {
curMetrics.swapCnt++;
double tmp = values;
values = values[j];
values[j] = tmp;
}

/** Extended classes implement this -- used by sort */
protected abstract void doSort();
}

 

[Oliver Wong]

I like your second solution, but there's no danger of recursively
calling sort() method?

I haven't actually tested it, but my guess is that if you try to cheat
by calling sort again recursively, the cheater will get the metrics for its
cheat-sort, and the original client will get the metrics for the
cheating-sort. I hope that wasn't too confusing.

Anyways, here's my solution. I actually have it so that they can call
sort() and it will resort. It just prevents recursively calling the
function. I just thought resorting by instantiating a new object would
be too restrictive in the 'real world', (of course, in the real world,
I'd also worry about multi-threading.)

[code snipped]

I only took a brief look at your code. The only comment I have has to do
with your "throw new IllegalStateException( );" followed by some comments
that explain why the exception is being thrown. I recommend you take those
comments, turn it into a string, and make that string be the parameter to
the constructor of IllegalStateException that you are invoking. I.e.:

throw new IllegalStateException("Not allowed to call sort() recursively.
This is to prevent doSort() etc...");

That way, if someone innocently calls sort recursively, they'll get a
message explaining why they aren't allowed to do so, rather than having to,
for example, come onto a newsgroup and post "Hey, has anyone gotten this
IllegalStateException when trying to recursively sort before? What does it
mean?"

- Oliver

 

[Chris Uppal]

Ok, I forgot to check if I am inside (ie. getDataLength() ==0), but
that was left as an
exercise to the reader

Sure, but I did want to emphasise that "super" didn'[t mean what your code make
it look as if it did (remember that this thread is about learning Java).

BTW, the values field is updated, but it is private. The main method
prints out the
array it gave as a parameter. So that is not an argument.

Ah yes. I missed that. (I was seeing what I expected the code to say, not
what it really did -- poor practise, especially in a "security" context). That
code in main is -- of course -- totally broken and should be fixed.

try { super.sort(null); } catch(Throwable skipping) {}

Now that, I /really/ like. Very neat. Especially if sort() were coded to copy
the parameter array before sorting (as it probably should do if we are taking
it as an example of writing malice-proof code, even though it's not necessary
in this specific case).

-- chris