SECURITY FLAW IN ONLINE JUDGE

General topic about Valladolid Online Judge

Moderator: Board moderators

bery olivier
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:

Post by bery olivier »

As we often get a hudge number of lines of input to handle, ranklist would probably be messed up with radom input.
But still, "a malicious hacker with lots of time on her hands"(Image) can get the the input. So She could do a source only containing ouput functions (I mean only printf or cout or println or system.out....)Image.
So I guess that a compromise is to ranodomise a little part of the input (e.g. : on an input with some thousands of lines consisting each of many numbers or strings, up to ten (digits Xor caracters) can be changed).
The probability to favour or handicap algorithms is not really high.
Let see what you think about it. Image
Not AC yet Image AC at last Image

SilVer DirectXer
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

Post by SilVer DirectXer »

oh shamim, you must in a ACM team of a Uni, ha~

pc2 is the submittion program for "real" ACM competition, i remember...written in Java..

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

to bery olivier

Post by Ivor »

But still, "a malicious hacker with lots of time on her hands"() can get the the input. So She could do a source only containing ouput functions (I mean only printf or cout or println or system.out....)
If you keep stating that one could hack his way through some thousand lines of input then go ahead and prove it! I personally don't believe that this is possible, maybe in case of having input the size of say 100 lines at max. But there are not many such problems on the site as far as I know.
So I guess that a compromise is to ranodomise a little part of the input (e.g. : on an input with some thousands of lines consisting each of many numbers or strings, up to ten (digits Xor caracters) can be changed).
The probability to favour or handicap algorithms is not really high.
Any randomizing of input leads to very imprecise timings. And it will totally screw up ranklists. They won't show anything about algorithm efficiency. Even at the moment one can't judge it very well -- improved IO techniques are messing it up a bit.

But let me give you an example. Let's take problem no. 100. It's fairly simple. Say you had the simplest approach of always calculating the cycle lengths within given range. This should have a running time of 3-6 seconds as far as I know. Now, lets say one created randomized input generator which everytime gives, say, 10000 lines. But in some freak way -- or by Murphy's laws, if you prefer -- one of the solutions gets 10000 intervals below 100000 with, say, maximum length of 100 elements. The other one gets 10000 intervals over 100000 and with maximum length of 10000 elements. Now how precise will the timing be if you have two identical solutions but will get two so different freak testcases?? The first one will run thousands of times faster than the other. (Well maybe it's not that precise but I think you get my point)

One can counter this example by suggesting to create a good input generator which will give even intervals, etc. But can you understand that creating a good input generator is far more complex task than the given problem actually might be? You can have good generators for simple problems like 100 but there are many complex tasks, and running time depends on individual test cases. Take numbers and primality tests -- time spent on testing does depend on primality of the number.

So basically my point is that there should be no randomized input for every solution submitted. Just a common input which is sometimes updated. Just like it is. It works perfectly fine and gives fairly objective results. And besides, who would take up the task of writing input generators for all 1000+ problems??? Every problem must be considered individually! Would you? I personally wouldn't!

Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Re: to bery olivier

Post by minskcity »

Ivor wrote:Any randomizing of input leads to very imprecise timings. And it will totally screw up ranklists. They won't show anything about algorithm efficiency.
I absolutely agree with that.
The only good thing about random input is that it can be stricter - it might find more mistakes in your code. At the moment judge accepts lots of incorrect solutions.
On the other hand judge based on random input can be unpredictable - refuse almost correct solution and accept very wrong algorithms. :-?
Does anybody know how to generate absolutely random numbers using a computer? :wink:

fpnc
System administrator
Posts: 201
Joined: Sun Oct 07, 2001 2:00 am
Location: Valladolid, Spain

Post by fpnc »

minskcity wrote:At the moment judge accepts lots of incorrect solutions.
About this kind of sentences, all that I have to say is that we need help. We cannot do everything. It helps to have an input-generator for each problem, if you want us to review the inputs every now and then. Believe me, there are problems which are very difficult to have inputs for.

About the randomness (?) of the input, all that I can say is that we do have a lot of things better to do than that. Also, as some of you have noted, I think it wouldn't be of any help (for example, ranklists will be messed up as you have noted before).

I hope timing differences will be reduced now, as web server will be hosted in a different machine than the judge, and the judge will not have too much load (I hope).
Best regards,

Fernando N

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise »

Given that many problems have multiple test-cases input, how about randoming thoses test-cases, i.e. always the same test cases, but not in the same order. That shouldn't modify in any way the running time (given that I don't think the answer for case B should be time-dependent of case A, except some rare problems with memoization all along the cases, but anyway the amount of calculus will be the same, so the time would be roughly unchanged), and it would prevent hackers from getting the input set.

Moreover, a hacker could automatizate the obtention of the input by using procmail on his mail server, that would forward the judge answer for the nth bit to a program that would analyse it, store the result, and make and sumbit the new source for the n+1th bit. This way, the only thing he'd had to do would be to parameter the number of the problem, and "go go go !", let it run.

Of course, I guess that there are many other things to do before (the randomization of input test cases would imply the modularization of the inputs, wich would I guess be a *huge* work for all the 1500 problems). Nevertheless, it's theorically interesting.

Anyway, those stupid hackers wouldn't be able to do it at the real ACM-ICPC contest, so why bother ? Okay, they're higher on the ranking list, and it's frustrating :/

Rene
New poster
Posts: 13
Joined: Mon May 05, 2003 4:40 am
Location: Shanghai,China

Post by Rene »

/*
* @(#)InternalFrameDemo.java 1.4 99/10/19
*
* Copyright (c) 1997-1999 by Sun Microsystems, Inc. All Rights Reserved.
*
* Sun grants you ("Licensee") a non-exclusive, royalty free, license to use,
* modify and redistribute this software in source and binary code form,
* provided that i) this copyright notice and license appear on all copies of
* the software; and ii) Licensee does not utilize the software in a manner
* which is disparaging to Sun.
*
* This software is provided "AS IS," without a warranty of any kind. ALL
* EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, INCLUDING ANY
* IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE OR
* NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN AND ITS LICENSORS SHALL NOT BE
* LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING
* OR DISTRIBUTING THE SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR ITS
* LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT,
* INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER
* CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF
* OR INABILITY TO USE SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGES.
*
* This software is not designed or intended for use in on-line control of
* aircraft, air traffic, aircraft navigation or aircraft communications; or in
* the design, construction, operation or maintenance of any nuclear
* facility. Licensee represents and warrants that it will not use or
* redistribute the Software for such purposes.
*/


import javax.swing.*;
import javax.swing.event.*;
import javax.swing.text.*;
import javax.swing.border.*;
import javax.swing.colorchooser.*;
import javax.swing.filechooser.*;
import javax.accessibility.*;

import java.awt.*;
import java.awt.event.*;
import java.beans.*;
import java.util.*;
import java.io.*;
import java.applet.*;
import java.net.*;

/**
* Internal Frames Demo
*
* @version 1.4 10/19/99
* @author Jeff Dinkins
*/
public class InternalFrameDemo extends DemoModule {
int windowCount = 0;
JDesktopPane desktop = null;

ImageIcon icon1, icon2, icon3, icon4;
ImageIcon smIcon1, smIcon2, smIcon3, smIcon4;

public Integer FIRST_FRAME_LAYER = new Integer(1);
public Integer DEMO_FRAME_LAYER = new Integer(2);
public Integer PALETTE_LAYER = new Integer(3);

public int FRAME0_X = 15;
public int FRAME0_Y = 280;

public int FRAME0_WIDTH = 320;
public int FRAME0_HEIGHT = 230;

public int FRAME_WIDTH = 225;
public int FRAME_HEIGHT = 150;

public int PALETTE_X = 375;
public int PALETTE_Y = 20;

public int PALETTE_WIDTH = 260;
public int PALETTE_HEIGHT = 230;

JCheckBox windowResizable = null;
JCheckBox windowClosable = null;
JCheckBox windowIconifiable = null;
JCheckBox windowMaximizable = null;

JTextField windowTitleField = null;
JLabel windowTitleLabel = null;


/**
* main method allows us to run as a standalone demo.
*/
public static void main(String[] args) {
InternalFrameDemo demo = new InternalFrameDemo(null);
demo.mainImpl();
}

/**
* InternalFrameDemo Constructor
*/
public InternalFrameDemo(SwingSet2 swingset) {
super(swingset, "InternalFrameDemo", "toolbar/JDesktop.gif");

// preload all the icons we need for this demo
icon1 = createImageIcon("ImageClub/misc/fish.gif", getString("InternalFrameDemo.fish"));
icon2 = createImageIcon("ImageClub/misc/moon.gif", getString("InternalFrameDemo.moon"));
icon3 = createImageIcon("ImageClub/misc/sun.gif", getString("InternalFrameDemo.sun"));
icon4 = createImageIcon("ImageClub/misc/cab.gif", getString("InternalFrameDemo.cab"));

smIcon1 = createImageIcon("ImageClub/misc/fish_small.gif", getString("InternalFrameDemo.fish"));
smIcon2 = createImageIcon("ImageClub/misc/moon_small.gif", getString("InternalFrameDemo.moon"));
smIcon3 = createImageIcon("ImageClub/misc/sun_small.gif", getString("InternalFrameDemo.sun"));
smIcon4 = createImageIcon("ImageClub/misc/cab_small.gif", getString("InternalFrameDemo.cab"));

// Create the desktop pane
desktop = new JDesktopPane();
getDemoPanel().add(desktop, BorderLayout.CENTER);

// Create the "frame maker" palette
createInternalFramePalette();

// Create an initial internal frame to show
JInternalFrame frame1 = createInternalFrame(icon1, FIRST_FRAME_LAYER, 1, 1);
frame1.setBounds(FRAME0_X, FRAME0_Y, FRAME0_WIDTH, FRAME0_HEIGHT);

// Create four more starter windows
createInternalFrame(icon1, DEMO_FRAME_LAYER, FRAME_WIDTH, FRAME_HEIGHT);
createInternalFrame(icon3, DEMO_FRAME_LAYER, FRAME_WIDTH, FRAME_HEIGHT);
createInternalFrame(icon4, DEMO_FRAME_LAYER, FRAME_WIDTH, FRAME_HEIGHT);
createInternalFrame(icon2, DEMO_FRAME_LAYER, FRAME_WIDTH, FRAME_HEIGHT);
}



/**
* Create an internal frame and add a scrollable imageicon to it
*/
public JInternalFrame createInternalFrame(Icon icon, Integer layer, int width, int height) {
JInternalFrame jif = new JInternalFrame();

if(!windowTitleField.getText().equals(getString("InternalFrameDemo.frame_label"))) {
jif.setTitle(windowTitleField.getText() + " ");
} else {
jif = new JInternalFrame(getString("InternalFrameDemo.frame_label") + " " + windowCount + " ");
}

// set properties
jif.setClosable(windowClosable.isSelected());
jif.setMaximizable(windowMaximizable.isSelected());
jif.setIconifiable(windowIconifiable.isSelected());
jif.setResizable(windowResizable.isSelected());

jif.setBounds(20*(windowCount%10), 20*(windowCount%10), width, height);
jif.setContentPane(new ImageScroller(this, icon, 0, windowCount));

windowCount++;

desktop.add(jif, layer);

// Set this internal frame to be selected

try {
jif.setSelected(true);
} catch (java.beans.PropertyVetoException e2) {
}

jif.show();

return jif;
}

public JInternalFrame createInternalFramePalette() {
JInternalFrame palette = new JInternalFrame(
getString("InternalFrameDemo.palette_label")
);
palette.putClientProperty("JInternalFrame.isPalette", Boolean.TRUE);
palette.getContentPane().setLayout(new BorderLayout());
palette.setBounds(PALETTE_X, PALETTE_Y, PALETTE_WIDTH, PALETTE_HEIGHT);
palette.setResizable(true);
palette.setIconifiable(true);
desktop.add(palette, PALETTE_LAYER);

// *************************************
// * Create create frame maker buttons *
// *************************************
JButton b1 = new JButton(smIcon1);
JButton b2 = new JButton(smIcon2);
JButton b3 = new JButton(smIcon3);
JButton b4 = new JButton(smIcon4);

// add frame maker actions
b1.addActionListener(new ShowFrameAction(this, icon1));
b2.addActionListener(new ShowFrameAction(this, icon2));
b3.addActionListener(new ShowFrameAction(this, icon3));
b4.addActionListener(new ShowFrameAction(this, icon4));

// add frame maker buttons to panel
JPanel p = new JPanel();
p.setLayout(new BoxLayout(p, BoxLayout.Y_AXIS));

JPanel buttons1 = new JPanel();
buttons1.setLayout(new BoxLayout(buttons1, BoxLayout.X_AXIS));

JPanel buttons2 = new JPanel();
buttons2.setLayout(new BoxLayout(buttons2, BoxLayout.X_AXIS));

buttons1.add(b1);
buttons1.add(Box.createRigidArea(HGAP15));
buttons1.add(b2);

buttons2.add(b3);
buttons2.add(Box.createRigidArea(HGAP15));
buttons2.add(b4);

p.add(Box.createRigidArea(VGAP10));
p.add(buttons1);
p.add(Box.createRigidArea(VGAP15));
p.add(buttons2);
p.add(Box.createRigidArea(VGAP10));

palette.getContentPane().add(p, BorderLayout.NORTH);

// ************************************
// * Create frame property checkboxes *
// ************************************
p = new JPanel() {
Insets insets = new Insets(10,15,10,5);
public Insets getInsets() {
return insets;
}
};
p.setLayout(new GridLayout(2,2));


windowResizable = new JCheckBox(getString("InternalFrameDemo.resizable_label"), true);
windowClosable = new JCheckBox(getString("InternalFrameDemo.closable_label"), true);
windowIconifiable = new JCheckBox(getString("InternalFrameDemo.iconifiable_label"), true);
windowMaximizable = new JCheckBox(getString("InternalFrameDemo.maximizable_label"), true);

p.add(windowResizable);
p.add(windowClosable);
p.add(windowIconifiable);
p.add(windowMaximizable);

palette.getContentPane().add(p, BorderLayout.CENTER);


// ************************************
// * Create Frame title textfield *
// ************************************
p = new JPanel() {
Insets insets = new Insets(0,0,10,0);
public Insets getInsets() {
return insets;
}
};

windowTitleField = new JTextField(getString("InternalFrameDemo.frame_label"));
windowTitleLabel = new JLabel(getString("InternalFrameDemo.title_text_field_label"));

p.setLayout(new BoxLayout(p, BoxLayout.X_AXIS));
p.add(Box.createRigidArea(HGAP5));
p.add(windowTitleLabel, BorderLayout.WEST);
p.add(Box.createRigidArea(HGAP5));
p.add(windowTitleField, BorderLayout.CENTER);
p.add(Box.createRigidArea(HGAP5));

palette.getContentPane().add(p, BorderLayout.SOUTH);

palette.show();

return palette;
}


class ShowFrameAction extends AbstractAction {
InternalFrameDemo demo;
Icon icon;


public ShowFrameAction(InternalFrameDemo demo, Icon icon) {
this.demo = demo;
this.icon = icon;
}

public void actionPerformed(ActionEvent e) {
demo.createInternalFrame(icon,
getDemoFrameLayer(),
getFrameWidth(),
getFrameHeight()
);
}
}

public int getFrameWidth() {
return FRAME_WIDTH;
}

public int getFrameHeight() {
return FRAME_HEIGHT;
}

public Integer getDemoFrameLayer() {
return DEMO_FRAME_LAYER;
}

class ImageScroller extends JScrollPane {

public ImageScroller(InternalFrameDemo demo, Icon icon, int layer, int count) {
super();
JPanel p = new JPanel();
p.setBackground(Color.white);
p.setLayout(new BorderLayout() );

p.add(new JLabel(icon), BorderLayout.CENTER);

getViewport().add(p);
}

public Dimension getMinimumSize() {
return new Dimension(25, 25);
}

}


}
[/java]
Le roi c'est loi,le loi c'est roi

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor »

Moreover, a hacker could automatizate the obtention of the input by using procmail on his mail server, that would forward the judge answer for the nth bit to a program that would analyse it, store the result, and make and sumbit the new source for the n+1th bit. This way, the only thing he'd had to do would be to parameter the number of the problem, and "go go go !", let it run.
Where do you take this theoretical hacker?? Are there really people out there who wish to hack this site? Yes, it IS a theoretical possibility but is there anybody dumb enough to try your way out? Look at it this way:
1. making such an input tester is a bit of work
2. you can't use it for any problem, maximum output must be below 40k and it must be a simple relation from input -> output
3. such testing will immediately occur to be suspicious as it will show on real-time status page

I just want to show you that if anybody is indeed dumb enough to do so he won't get much. You must agree that it isn't worth trying out.

Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

bery olivier
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:

Post by bery olivier »

There is a lot of people register here. How can we be sure that none of the 33000 users will try this well known way.
If she/he tests many problems in the same time, we cannot see it. We cannot be suspicious against the ones whitch submit ten differents problem, and again the same ten and so on.
Morover, she/he can use lot of accounts to do it faster and safer.
Not AC yet Image AC at last Image

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise »

Ivor wrote: Where do you take this theoretical hacker?? Are there really people out there who wish to hack this site? Yes, it IS a theoretical possibility but is there anybody dumb enough to try your way out?
Hi Ivor

Of course, that was only for the pleasure to think about it. I was simply theorizing :)
I guess the only one who would do such a thing would be somebody like people posting on this thread : problem solvers, who would only do that to see if it can be easily done. And of course, the Real time status would automatically give alert (if we don't use many accounts, and use a loooooooong time).

To summariez : that was only for theorical interest, I never imagined somebody would REALLY do that lol :lol:

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

Actually I can't see a point in begin so afraid of that "attack". If one decides to try it then what? Why should we care? (of course if it doesn't affect the judging maschine).

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor »

If she/he tests many problems in the same time, we cannot see it. We cannot be suspicious against the ones whitch submit ten differents problem, and again the same ten and so on.
Morover, she/he can use lot of accounts to do it faster and safer.
I said it and I repeat it again -- it's not worth even trying. Think and look it up: how many problems are there for which you could get output in such a way. Then estimate how many input lines will there be for output at max 40k. Then think how many different inputs/answers you will have to try!! For sake! You will not manage to get an answer! You might get a problem or ten soved in a month (maybe) using this method. And most of the problems you solve in this way will have anyway (not necessarily but I believe most) 0.000 time. So, why bother?

Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

El-idioto
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands

Post by El-idioto »

Hi all,

Forgive me for stating some obvious points:

1.
Previously, someone was worried that through hacking the site (obtaining the input file for a problem) the time taken to complete the problem would be very low.
Doesn't the machine of the online judge change from time to time? Then, all the timings will be useless anyway.

2.
Who cares about cheaters?!? I've discovered this site 4 days ago, and have so far solved the first 4 problems. If others are cheating, I don't mind... I just want to solve them myself for the fun of it.
Also, I wouldn't be surprised if a couple (a lot?) of people cheat by using an alternate log in to submit their code, and after acceptance submit it through their main log in. (I noticed some people had a perfect score, i.e., #submissions == #accepted).
Finally, it seems likely to me that some of the log ins are in fact groups of people (I mean, the current leader has solved 1174 problems... that seems a bit much for a single person).

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

You're right that sometimes many people send their solutions as one user. But it's nothing new as names like XXX University ACM Team are quite common.

This doesn't allow you to say that "someone did that many problems so other guys must have helped him". It's simply not true because if you're good then 20-30 minutes will be enough to solve a task, lets lay 60 if it is a difficult one. Multiply it by a few years and you get a thousand easily.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

I also think, that people from best 50 don't cheat and don't send solutions in groups .... And I agree with Krzysztof - it's easy to get 1000 or more problems in a few years if you have a few hours every day :):)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Post Reply

Return to “General”