The 'perfection challenge' for a level (at whatever difficulty level you fancy) is basically to trigger and kill all enemies as you go through it, with no reversion and without ever losing a bar of health. The full rules I follow are the same as for my kill 'em all speed runs except that you can't lose health. You can try it at speed if you like, but that's mighty stressful. I usually take my time.
With the perfection challenge, fighting tends to be quite a bit different from normal fighting. Tactics you'd normally use will often need to be replaced by lower risk tactics that you'll need to develop. You'll also need to be more clinical in your execution. With a speed run in particular, it's probably some of the best practice you could get for making yourself sharper. It's taught me quite a bit, and if you like thinking about tactics you should enjoy it a lot. Because of the difference from normal fighting, it sort of makes the level fascinating all over again.
On Legendary you'll need to play extra cautiously, particularly when you encounter Elites. Prepare to be extremely annoyed with yourself when a momentary lapse of concentration loses you a health bar after an hour's worth of careful progress! It's going to be a real test of perseverance. If it gets too aggravating though, you could make things a bit less severe by just trying to get to the end without using a medkit (in which case you'll have to be very careful not to step over one, once you've lost some health).
Some of my own attempts
Moving on to some good honest bragging, my best achievement so far with this challenge was probably my speed run of 'Two Betrayals' on Legendary in 81 minutes (after many attempts and a gradual fine-tuning of tactics), except that this was with an earlier version of my kill 'em all rules in which Sentinels were allowed to be skipped - something I've since changed.
But it's so easy to foul up. In one earlier run when I was nicely on course for a new record time, I'd just finished off the Flood in the underground bridge area, except there was still a gurgle off to my left when I was near the end of the bridge. Where the heck is that coming from, I thought. So I foolishly went over to the side to take a look, without really thinking it through. In a brief moment I saw an ex-Elite Flood down on one of the pipes sticking out of the chasm side; presumably he'd got blown down there. And no sooner had I spotted his rocket launcher than he fired it. An image of the rocket streaking towards me was burned into my memory for all perpetuity, and it was such a shock that I ducked hard for real. Ever done that? Predictably, this evasive action was not as effective as using the joystick. And BLAM! The rocket hit the bridge and I was blown into little cyborg pieces. Doh! Back to the drawing board…
Another time I suffered Death By Grunt. Oh the shame! Mind you, he did have a fuel rod gun. He got me when I was in a Banshee, miles away, just prior to the second generator room. Accurate little blighter! It's not the first time I've underestimated one of those fuel rod Grunts.
Somewhat earlier I managed level 5 on Legendary. That wasn't a speed run though, and I took over 3 hours. Since then I've tried speed runs. Best time so far is just over 113 minutes, but I think I can significantly improve that if I push a bit harder.